Median Sorting

MedianSorting


=============================================================
 

MEDIAN SORT(DIVIDE AND CONQUER) algorithm sorts an
array A of n≥1 elements by swapping the median element A[me] with the middle
element of A , creating a left and right half of the array. MEDIAN SORT
then swaps elements in the left half that are larger than A[mid] with elements in
the right half that are smaller or equal to A[mid]

Median   Sort Complexity
Best O(n log n)
Average O(n log n)
Worst  O(n^2)


=================================================================
Median Sort Algorithm

Sort(Array)
for i=1to n-1 do
medianSort(Array,0,n-1)
end

medianSort(Array,left,right)
if(left<right) then
find Median value Array[median] in Array[left,right]
mid=(right+left)/2
swap Array[mid] and Array[median]
for i=left to mid-1 do
if(Array[i]>Array[mid])then
find Array[k] <=Array[mid] where k>mid
swap A[i] and A[k]
medianSort(Array,left,mid-1)
medianSort(Array,mid+1,right)
end
===========================================================================================

--
ANish