title: Understanding quicksort
body: <p>I'm having a hard time understanding quicksort, most of the demonstrations and explanations leave out what actually happens (<a href="http://me.dt.in.th/page/Quicksort/" rel="noreferrer">http://me.dt.in.th/page/Quicksort/</a> for example).</p>
  
  <p>Wikipedia says:</p>
  
  <blockquote>
    <p>Pick an element, called a pivot, from the array. Partitioning: reorder
    the array so that all elements with values less than the pivot come
    before the pivot, while all elements with values greater than the
    pivot come after it (equal values can go either way). After this
    partitioning, the pivot is in its final position. This is called the
    partition operation. Recursively apply the above steps to the
    sub-array of elements with smaller values and separately to the
    sub-array of elements with greater values.</p>
  </blockquote>
  
  <p>How would that work with an array of 9,1,7,8,8 for example with 7 as the pivot? The 9 needs to move to the right of the pivot, all quicksort implementations are in place operations it seems so we can't add it after the 8,8, so the only option is to swap the 9 with the 7.</p>
  
  <p>Now the array is 7,1,9,8,8. The idea behind quicksort is that now we have to recursively sort the parts to the left and right of the pivot. The pivot is now at position 0 of the array, meaning there's no left part, so we can only sort the right part. This is of no use as 7>1 so the pivot ended up in the wrong place.</p>
  
  <p>In this image 4 is the pivot, then why is 5 going almost all the way to the left? It's bigger than 4! After a lot of swapping it ends up being sorted but I don't understand how that happened.</p>
  
  <p><a href="https://i.stack.imgur.com/xq1sz.png" rel="noreferrer"><img src="https://i.stack.imgur.com/xq1sz.png" alt="https://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Quicksort-diagram.svg/400px-Quicksort-diagram.svg.png"></a></p>