0. Problem

We want to make a function called QuickSort to sort the array and return it.

quickSort(arr)

1. Recursion

QuickSort takes a random value in the array and moves everything less than it to its left, and everything greater than it to its right. We can do this in $O(n)$. This is called "partitioning" the array. Below we randomly pick the number $\tt 5$ to partition the array.

The array isn't sorted after partitioning, but now the $\tt 5$ is in the right place, and everything to the left belongs on the left, and same for the right. To sort the whole array, we can just repeat the process on the left and right sides.

# quickSort(i, j) sorts the numbers in `arr` between index i and j
quickSort(i, j) = {
    # pick a random value, and partition arr[i...j] on it
    # `pL` and `pR` are the new leftmost and rightmost indices of the value, to account for duplicates 
    val = arr[random.randrange(i, j+1)]
    pL, pR = partition(arr, i, j, val)

    # repeat for the left side (i...pL-1) and right side (pR+1...j)
    quickSort(i, pL-1)
    quickSort(pR+1, j)
}

2. Base case

The recursion should stop when the two pointers cross.

if j == i-1:
    return

3. Code

def quickSort(arr):
    
    def quickSort(i, j):

        # base case
        if j == i-1:
            return
        
        # recursion
        val = arr[random.randrange(i, j+1)]
        pL, pR = partition(arr, i, j, val)

        quickSort(i, pL-1)
        quickSort(pR+1, j)
    
    quickSort(0, len(arr)-1)

Time Complexity $O(n \log n)$ average. It's $O(n^2)$ worst-case because you might get very unlucky with the values you pick in your partition, doing an $O(n)$ operation each time (consider always partitioning the smallest element).

Space Complexity $O(n)$. Everything is in-place, but the Call Stack gets somewhere between $\log n$ to $n$ calls deep. Even if you converted to iterative you'd need a stack that grows this big.

Partition Implementation

Here's how you implement partition, also called the "Dutch National Flag problem".

Partition would be easy if we used extra memory, but the hard part is doing it in-place without extra memory. The trick is to start a pointer c on the left, and walk left to right, gradually partitioning the array as you walk.

For example, you start like this:

As you walk, you swap elements from the opposite side of the array if needed.

The value you're partitioning might show up multiple times, so you have to keep track of the left and right locations of the value as you walk, which we'll call pL and pR. You can do this by growing pL and pR from the left and right sides of the array as you walk. You just need to make sure everything from 0...pL is less than the value, everything between pL and c is equal to the value, and everything on the right from pR and on is greater than the value.

The stopping point is when c and pR cross.

Here's the code for partition:

def partition(arr, i, j, val):
    pL = i
    pR = j
    c = pL

    # iterate over every index c
    while pR != c-1:
        # swap arr[c] into the left side
        if arr[c] < val:
            arr[c], arr[pL] = arr[pL], arr[c]
            pL += 1
            c += 1
        # swap arr[c] into the right side
        elif arr[c] > val:
            arr[c], arr[pR] = arr[pR], arr[c]
            pR -= 1
        # do nothing
        else:
            c += 1
    return pL, pR

Here's the full code:

Open SpoilerClose Spoiler

import random

def partition(arr, i, j, val):
    pL = i
    pR = j
    c = pL

    # iterate over every index c
    while pR != c-1:
        # swap arr[c] into the left side
        if arr[c] < val:
            arr[c], arr[pL] = arr[pL], arr[c]
            pL += 1
            c += 1
        # swap arr[c] into the right side
        elif arr[c] > val:
            arr[c], arr[pR] = arr[pR], arr[c]
            pR -= 1
        # do nothing
        else:
            c += 1
    return pL, pR




def quickSort(arr):
    def quickSort(i, j):
        if j == i-1:
            return
        # partition i...j on `val`
        val = arr[random.randrange(i, j+1)]
        pL, pR = partition(arr, i, j, val)

        # now, repeat for the left side (i...pL-1) and right side (pR+1...j)
        quickSort(i, pL-1)
        quickSort(pR+1, j)
    
    quickSort(0, len(arr)-1)

Unimportant details:

Open SpoilerClose Spoiler

If you're curious, this has a historical name - Hoare partitioning. It's faster than Lomuto, the common alternative. We don't like that there's so much jargon when you Google these, though - they're both just simple algorithms.