Quicksort

A divide and conquer recursive algorithm.

Quicksort is a commonly used sorting algorithm that has a best-case time complexity of O(n log n) and worst-case of O(n²). The worst-case happens when the array to be sorted is already sorted or nearly sorted.

Quicksort works by selecting an element in the array as the ‘pivot’ and then dividing the array into two partitions. One partition for values less than the pivot and one partition for those that a greater.

Today we will be looking at a quicksort implementation that handles the sorting of an array of integers but it can easily be adapted to sort anything with the right comparison function.

Edge Cases

1. An empty array or an array with only 1 element is unsortable so return the input array.

Now I’m going to create a length variable (for convenience), the pivot, and both partitions which we will be recursively sorting. I’m setting the pivot to be the last element in the array for simplicity but there are other more complex but also more efficient ways of setting the pivot. See Hoare partition scheme.

Now that our partitions are setup we can iterate over the array placing values lower than the pivot in the left partition and values greater than the pivot in the right partition.

Now we have a semi-sorted array with a left partition, pivot, and right partition. All that's left is to sort the left and right partitions recursively and concatenate them.

This algorithm is fast when given arrays that are not already sorted. This is however a simple implementation of quicksort with a lot of room for optimization.

The partitioning in this implementation of quicksort creates two new arrays in memory on every function call, this can add up if you have a large input array. If you don’t mind directly mutating the input array you can save a lot of memory by swapping the elements around in the original array during the partitioning instead of creating new empty arrays to push to.

Here’s the same quicksort implementation in Python.