title: Why choose a random pivot in quicksort
body: <p>So choosing a pivot at random has O(n<sup>2</sup>) running at worst case but when the pivot is chosen as the average of min value and max value of the list you get a worst case O(n log n).</p>
  
  <p>Of course there are the added 2*O(n) on each recursion due to finding the min and max values as opposed to the constant O(1) of the random generator has. When implementing this as the pivot you get the list sorted at the leaves of the recursion tree instead in the standard algorithm elements get sorted from the root to leaves.</p>
  
  <p>When implementing instead of the pivot being a value on the list it is just a number compared to so this is not the standard quicksort but my question still applies. </p>
  
  <p>Below is my poorly written pseudo code:</p>
  
  <pre><code>func sort(List n):
      if n.length &lt; 2
       return n;
      min = n.minValue
      max = n.maxValue
      avg = (min+max) /2 
      List left = list of elements in n less than avg
      List right = list of elements in n greater than avg
      sort(left)
      sort(right)
  </code></pre>