Quicksort is one of the most popular algorithms of all time because. While in running time it performs the same as merge sort, it sorts in place so does not come with significant space overhead.

However, the algorithm is not trivial and requires detailed analysis to understand why it reaches $O(N \log{N})$ run time.

Quicksort is a divide and conquer algorithm where the divide step is non-trivial. However, this makes the merge sort algorithm simple.

Partitioning

At its core, it's beautifully simple: take some collection of elements and rearrange them so that elements satisfying some property end up on one side, and elements not satisfying it end up on the other.

Think of partitioning as a filtering operation that's done in-place. You're not creating new arrays; you're cleverly rearranging elements using the space you already have.

The Lomuto partition scheme is easiest to understand. You maintain a boundary between "small" and "unprocessed" elements:

partition(A, low, high):
    pivot = A[high]
    i = low - 1  // boundary of small elements
    
    for j from low to high-1:
        if A[j] <= pivot:
            i++
            swap A[i] with A[j]
    
    swap A[i+1] with A[high]
    return i+1

The partitioning algorithm always returns the number of elements smaller than the pivot.

The invariant is key: at every step, everything from low to i is ≤ pivot, everything from i+1 to j-1 is > pivot, and everything from j onward is unprocessed. The partitioning algorithm is one of the best illustration of the idea of invariants.

Note how we maintain two pointers: i and j so that we can rearrange elements within the space we have.

i → Boundary between lower and higher

j → The next element we want to add into the partition

Example Problems

Partitioning is the secret weapon behind quicksort, one of the fastest practical sorting algorithms.

It's central to selection algorithms that find the kth smallest element in linear time.

It appears in computational geometry, string algorithms, database query optimization, and even in how operating systems manage memory.

Linear Time Selection

This is a key application of partitioning. Refer to Quickselect .

Three way partitioning

This is incredibly useful when the data we are working with has a lot of duplicates (for example, sorting a list with 4 keys). This is to make sure the partition is effective.

This approach partitions the array and then partitions one of the two partitions produced.