title: Explanation of the Median of Medians algorithm
body: <p>The <code>Median of medians</code> approach is very popular in <code>quicksort</code> type partitioning algorithms to yield a fairly good pivot, such that it partitions the array uniformly. Its logic is given in Wikipedia as:</p>
  
  <blockquote>
    <p>The chosen pivot is both less than and greater than half of the elements in the list of medians, which is around n/10 elements (1/2 * (n/5)) for each half. Each of these elements is a median of 5, making it less than 2 other elements and greater than 2 other elements outside the block. Hence, the pivot is less than 3(n/10) elements outside the block, and greater than another 3(n/10) elements outside the block. Thus the chosen median splits the elements somewhere between 30%/70% and 70%/30%, which assures worst-case linear behavior of the algorithm.</p>
  </blockquote>
  
  <p>Can somebody explain it a bit lucidly for me. I am finding it difficult to understand the logic.</p>