medianSort

the median sort is a sorting algorithms similar to quick sort and trys to get better performance by choosing better pivot to avoid the worst case sinario that quick sort faces

the mechanism :

first call of the medSort will find the min and max items in the list, thats done using one loop and then call the the other medSort which input is the array,start point ,end point ,min item ,max item which is calculated before .

this method call will starts by calculating the median of the array portion form start to end which is equal to (min+max)/2 and then it will pass throw the array element by element and if the element is greater than the median it will be added to the end of the array .

the method will be re called for the left and the right side of the new array.

the termination will be done if the length of the array portion less that 2 or elements are equal which is represented by if (min==max)return; and if the length of the portion is 2 it will be swaped if needed and then return.

test

// bound of random 1000000000

1 million items

quicksort : 124 894 400ns enhanced medsort : 140 108 700ns

100k items

quicksort : 19 625 300 ns
medsort : 22 721 600 ns

1k items

quicksort : 1 411 900ns medsort : 1 581 900ns

100 000 random items

median sort : 49 389 900ns quick sort : 18 210 800ns

illustration:

first call

the items that are greater than the median are added last

recursive calls of left and right

right recursive call

left recursive call

final result