Quicksort Using Median of Medians as Pivot

Median of Median is an algorithm for selecting the kth largest element in an unordered list, having worst case linear time complexity [1]. It is based on the Hoare’s selection algorithm also called quickselect algorithm [6]. The Median of Median algorithm uses an asymptotically optimal approximate median selection algorithm to make an asymptotically optimal general search algorithm. It finds the approximate median in linear time which is then used as pivot in the quickselect algorithm. This approximate median can be used as pivot in Quicksort, giving an optimal sorting algorithm that has worst-case complexity O(n log n) [2]. This paper proposes variation in the above mentioned implementation technique for the median selection problem to find the Median of Medians and the value obtained is further used to guarantee a good pivot for the Quicksort algorithm. The result of the experiment performed show that the strategy proposed has worst-case complexity O(n log n) for Quicksort. Graphs were also plotted for the usual Quicksort function and the Quicksort function that uses the proposed median of median (PMOM) as pivot for relatively large values of size of array and results were compared. These confirm that proposed algorithm indeed has worst-case complexity O(n log n) for Quicksort.