Find the median of a sequence of n integers.

Question: Given a sequence of integers, find the median of the integers?

Input: arr [] = {15, 23, 4, 16, 8, 42}. Find median.
Output: 15

Since the question does not specify anything we cannot assume that the given array is a sorted one. The definition of median is the (n/2)^th element of a sorted sequence of integers.
This definition makes our approach simpler. All we need to do is sort the integers and then return the (n/2)^th element.
Here is the code for above approach. I use quick sort to sort the array.

#include<stdio.h>

void swap(int *i, int *j) {
	int temp = *i;
	*i = *j;
	*j = temp;
}

int partition(int arr[], int start, int end) {
	int pivot = arr[end];
	int i = start, j = end-1;
	while(i<=j) {
		while(arr[i]<pivot)    i++;
		while(arr[j]>pivot)    j--;
		if(i<=j) {
			swap(&arr[i],&arr[j]);
			i++;
			j--;
		}
	}
	swap(&arr[i],&arr[end]);
	return i;
}

void performQuickSort(int arr[], int start, int end) {
	if(start<end) {
		int p = partition(arr, start, end);
		performQuickSort(arr, start, p-1);
		performQuickSort(arr, p+1, end);
	}
}

void quickSort(int arr[], int size) {
	performQuickSort(arr, 0, size-1);
}

// driver program to find median
int main(void)
{
	int i;
	int arr[6] = {15, 23, 4, 16, 8, 42};
	int size = 6;

	quickSort(arr,size);

	printf("Median:- %d",arr[size/2]);

	return 0;
}

Time Complexity:- O (n*log (n)) due to quick sort.