15.4 Quick Sort Revisited

Problem

Merge sort guarantees (O(n \log n)) performance and stable ordering, but it requires additional memory proportional to the input size. For large datasets, memory allocation and copying can become significant costs.

Can we design a divide-and-conquer sorting algorithm that sorts data in place while maintaining excellent practical performance?

Solution

Use Quick Sort.

Quick sort partitions an array around a selected pivot element. After partitioning, all elements smaller than the pivot appear on one side, while all larger elements appear on the other. The pivot is then in its final sorted position.

The algorithm recursively sorts the two partitions.

Unlike merge sort, quick sort performs most of its work during division rather than during combination.

The combine phase is essentially free.

High-Level Idea

Consider:

[9, 4, 7, 3, 10, 5]

Choose:

pivot = 7

Partition:

[4, 3, 5] 7 [9, 10]

The pivot now occupies its final position.

Recursively sort:

[4, 3, 5]

and

[9, 10]

Result:

[3, 4, 5, 7, 9, 10]

The key insight is that once a pivot is placed correctly, it never needs to move again.

Partition Procedure

Partitioning rearranges elements around a pivot.

Starting array:

[9, 4, 7, 3, 10, 5]

Choose the last element as pivot:

pivot = 5

Scan the array.

Values less than 5 move left:

[4, 3, ?, ?, ?, 5]

Values greater than 5 move right:

[4, 3, 5, 7, 10, 9]

The pivot ends in position 2.

Everything left is smaller.

Everything right is larger.

The array has been divided into two independent subproblems.

Lomuto Partition Implementation

func partition(nums []int, low, high int) int {
    pivot := nums[high]

    i := low

    for j := low; j < high; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }

    nums[i], nums[high] = nums[high], nums[i]

    return i
}

After execution:

nums[low:i]

contains smaller values.

nums[i]

contains the pivot.

nums[i+1:high]

contains larger values.

Recursive Algorithm

func quickSort(nums []int, low, high int) {
    if low >= high {
        return
    }

    pivot := partition(nums, low, high)

    quickSort(nums, low, pivot-1)
    quickSort(nums, pivot+1, high)
}

The implementation is remarkably compact.

Most of the complexity lies inside partitioning.

Best-Case Analysis

Suppose each pivot splits the array evenly.

The recurrence becomes:

$$ T(n)=2T(n/2)+n $$

Partitioning requires:

$$ O(n) $$

work.

The Master Theorem gives:

$$ T(n)=\Theta(n\log n) $$

This matches merge sort.

Recursion Tree

Balanced partitioning produces:

                n
           /         \\n        n/2          n/2
       /  \          /  \\n    n/4  n/4     n/4   n/4

Each level performs:

$$ n $$

work.

Height:

$$ \log n $$

Total:

$$ \Theta(n\log n) $$

Worst-Case Analysis

Suppose the smallest element is always chosen as pivot.

Example:

[1,2,3,4,5,6,7]

Partitioning produces:

[] [2,3,4,5,6,7]

Only one side contains work.

The recurrence becomes:

$$ T(n)=T(n-1)+n $$

Expanding:

$$ n+(n-1)+(n-2)+\cdots+1 $$

gives:

$$ \Theta(n^2) $$

This is the classical worst case.

The recursion tree degenerates into a linked list.

Average-Case Analysis

Remarkably, random inputs rarely generate worst-case behavior.

The expected recurrence behaves much closer to:

$$ T(n)=2T(n/2)+n $$

than:

$$ T(n)=T(n-1)+n $$

Average performance becomes:

$$ \Theta(n\log n) $$

This explains quick sort's popularity.

In practice, average-case behavior matters far more than theoretical worst-case behavior.

Randomized Pivot Selection

A simple improvement is selecting a random pivot.

pivotIndex := low + rand.Intn(high-low+1)

Swap it into the pivot position and continue.

Randomization makes adversarial inputs extremely unlikely.

Expected running time remains:

$$ \Theta(n\log n) $$

regardless of input order.

This transformation is one of the most powerful examples of randomized algorithm design.

Median-of-Three Pivot

Many implementations choose the median of:

first
middle
last

elements.

Example:

[1,2,3,4,5,6,7,8,9]

Candidates:

1,5,9

Median:

5

This often approximates balanced partitioning without additional overhead.

Many production quicksort implementations use some variation of this idea.

Three-Way Partitioning

Standard partitioning performs poorly with many duplicate values.

Example:

[5,5,5,5,5,5,5]

Traditional quick sort repeatedly partitions nearly identical arrays.

Three-way partitioning divides into:

less than pivot
equal to pivot
greater than pivot

Example:

[3,2] [5,5,5,5,5] [8,7]

The middle section requires no further work.

This dramatically improves performance on duplicate-heavy datasets.

Space Complexity

Unlike merge sort:

Algorithm	Extra Space
Merge Sort	(O(n))
Quick Sort	(O(\log n)) average

Quick sort sorts in place.

Only recursion stack frames consume additional memory.

Balanced recursion:

$$ O(\log n) $$

Worst-case recursion:

$$ O(n) $$

Randomization largely prevents this scenario.

Cache Efficiency

Quick sort exhibits excellent locality.

Partitioning scans memory sequentially:

0 → 1 → 2 → 3 → ...

Modern CPUs aggressively optimize sequential access.

Merge sort often jumps between multiple arrays and temporary buffers.

As a result, quick sort frequently outperforms merge sort despite identical asymptotic complexity.

This is a classic example of the difference between theoretical and practical performance.

Introsort

Many standard libraries use Introsort.

Introsort begins as quick sort.

If recursion depth becomes suspiciously large:

$$ 2\log n $$

it switches to heap sort.

Advantages:

• Average-case speed of quick sort.
• Worst-case guarantee of heap sort.
• In-place operation.

The sorting routines in entity["software","C++ Standard Library","std::sort"] are based on this idea.

Common Mistakes

Poor Pivot Selection

Always choosing:

first element

or:

last element

can produce pathological behavior.

Infinite Recursion

Incorrect partition boundaries may repeatedly process the pivot.

Always exclude the pivot position from recursive calls.

Duplicate Values

Standard partitioning performs poorly on heavily duplicated inputs.

Three-way partitioning often solves this issue.

Stack Overflow

Deep recursion can exhaust stack space.

Randomized pivots and tail-recursion optimizations help mitigate this risk.

Discussion

Quick sort illustrates a different philosophy from merge sort. Merge sort divides perfectly and performs expensive merging later. Quick sort performs an expensive partition immediately and then benefits from nearly free combination. The resulting algorithm sacrifices worst-case guarantees but gains in-place operation, excellent cache locality, and exceptional real-world performance.

For many practical workloads, quick sort remains one of the fastest general-purpose sorting algorithms ever developed. Its partitioning strategy also forms the foundation of selection algorithms, order-statistics structures, database partitioning techniques, and several advanced divide-and-conquer algorithms explored later in this chapter.