Find the median of a set of positive integers

Find the median of a set of positive integers

Problem Definition:

          Consider a set of "N" positive numbers, the median can be found using following steps:

  1. Sort the set of positive numbers.
  2. If the number of elements is odd, the middle element is the median.
  3. Else if the number of elements is even, the average of middle two elements is the median.
Input: Given set of positive integers.

Output: Median of the set of given N integers.

Constraints:

  1. The numbers may or may not be contiguous.
  2. The numbers can range from 0 to 10^6.
  3. The numbers may or may not be sorted.
  4. The number of elements may be even or odd.
Example:

Case 1:
               Let the given positive of integers be 6,4,3,2,5
               To find the median, we have to sort the numbers using optimal sorting algorithm (of which I would prefer insertion sort, which have n/2 sorted elements while proceeding with n/2+1th unsorted element.
After sorting, the list would now look like 2,3,4,5,6 of which the median is the middle most element. i.e., "4"

Case 2:
               Let the given positive integers be 1,6,4,3,2,5
               Note that there is even number of elements in the list.
               After sorting, the list becomes, 1,2,3,4,5,6 of which middle most elements are "3" & "4". So, the median is the average of the two middle elements in this case.
               Hence,
                         "3" is the median.