Truly Understanding Quicksort

How it works – overview

The main part of the algorithm is the so-called partitioning step.

To partition an array, an element is arbitrarily chosen and called the pivot. There are many strategies for choosing a pivot, but for simplicity let us always choose the leftmost element.

             7 2 8 4 3 6 9
             ^
           pivot

The partitioning sub-algorithm moves all elements smaller than the pivot to the left and all elements larger than the pivot to the right:

After partitioning:

             2 4 3 6 7 8 9
                     ^
                   pivot

The elements to the right (left) can be in any order — what is important is that they are smaller (bigger) than the pivot.

After partitioning, the pivot is surely in its final position.

Array after partitioning:

             2 4 3 6 7 8 9
                     ^
                   pivot

Array as should be output:

             2 3 4 6 7 8 9
                     ^
                  where 7 goes in the sorted array

Each of the two subarrays, to the right and to the left, of the pivot are then sorted recursively:

                  sort right-hand side recursively
                       vvv
             2 4 3 6 7 8 9
             ^^^^^^^
     sort left-hand side recursively

Go to the next page for an overview of how to perform partitioning.