Quick sort median selection


You should look into the Median of Medians algorithm. It is a linear time algorithm with the following recurrence...

T(n) ≤ T(n/5) + T(7n/10) + O(n)

... which is O(n). The algorithm details...

  1. divide the list into n/5 subsequences of 5 elements each
  2. find the median of each list, by brute force. there will be n/5 of these
  3. Let m_1,..., m_n/5 be these medians.
  4. recursively find the median of these medians. this will be 1 element, the pivot!

... and some pseudo-code...

MedianOfMedians (A[1],...,A[n]) 
    for i=1 to n/5 do {
        let m_i be the median of A[5i − 4], A[5i − 3],..., A[5i];
    pivot = Select(m1,...,m_n/5, n/10); // the pivot
    return pivot


I hope this helps.

Author by


Updated on June 04, 2022


  • james
    james 7 months

    As we can choose median of 3 element partitioning to implement quick sort. Likewise can we choose median of 5, 7, or 11 element to implement quick sort? If so, then how??

  • Alcott
    Alcott over 11 years
    according to your code, we can just find the pivot closest to the median of the whole array, then partition the whole array into 2 parts? If the lower part has fewer numbers than the higher part, then do what ?