How Quicksort Works
Quicksort (especially in-place Quicksort) can be a bit confusing, so let’s walk through an example to show how this sorting algorithm works.
Suppose we are given the following array to sort:
Now let’s choose something called a “pivot point”. The goal is to rearrange the array such that all all elements less than the pivot are to its left, and all elements greater than the pivot are to its right. The choice of the pivot point is arbitrary; it can be the first element of the array, the last element of the array, or even a random element! For our purposes though, let’s choose the pivot point to be the last element in the array, 5.
After rearranging the array around the pivot point 5, we should obtain the following array:
We then recursively follow the above procedure for the subarrays to the left and to the right of the pivot point.
The subarray to the left of the pivot point is just one element. No point in sorting an array of length one, so there’s nothing to do here!
On the other hand, the subarray to the right of the pivot point is not so trivial. Following the procedure described above, let us choose 7 to be the new pivot point for this subarray.
After rearranging the elements of the subarray around the pivot point, we obtain the following:
By continuing recursively, and merging the left subarray with the pivot and the right subarray, a sorted array is returned.
