Quicksort: basic idea

• choose an item to be a "pivot"
• re-arrange (partition) the array so that
  • all elements to left of pivot are smaller than pivot
  • all elements to right of pivot are greater than pivot
• (recursively) sort each of the partitions