Sorting

Quick Sort

A divide-and-conquer sorting algorithm that chooses a pivot, partitions the array, and then recursively sorts the smaller parts.

Quick sort is fast in practice and powerful for teaching because one key operation creates structure: partition. Once partition is complete, the pivot lands in its final sorted position and never moves again.

The main learning flow is simple: Choose Pivot → Partition → Recurse. If learners understand what partition guarantees, recursion becomes much easier to follow.

Watch Visualization View Pseudocode

Quick Facts

Main Idea

Choose a pivot, move smaller values to one side and larger values to the other, then sort the smaller subarrays.

Partition Guarantee

After partition, the pivot is in its final sorted position.

Typical Strength

Quick sort is often very fast in practice and is widely used as a general-purpose sorting strategy.

Main Risk

Poor pivot choices can lead to highly unbalanced partitions and worse performance.

Key Idea

The heart of quick sort is the partition step. Partition is not random swapping. It rearranges the current subarray so values smaller than or equal to the pivot go to one side, and larger values go to the other side.

The most important mental model is: once the pivot locks into place, it is done forever. Then the algorithm repeats the same idea on the left and right subarrays.

Visualization

This visualization emphasizes three cues: pivot selection, partition swaps, and the moment the pivot locks into place. That lock is the core teaching moment of quick sort.

How It Works

Choose a Pivot

Select one value in the current subarray to act as the pivot. In this lesson, the pivot is the last element.

Partition the Subarray

Scan through the subarray and move values smaller than or equal to the pivot toward the left side.

Lock the Pivot

Place the pivot between the left and right regions. At that moment, the pivot is in its final position.

Recurse Left and Right

Apply the same process to the smaller subarrays on the left and right of the pivot.

Partition Example

A concrete partition example makes the idea much easier to understand:

Array: [4, 3, 1, 5, 2]
Pivot: 2

Compare each value to the pivot. Values smaller than or equal to 2 move left. Larger values stay on the right side.

After partition:
[1, 2, 4, 5, 3]

The key observation is that 2 is now in its final sorted position. The algorithm only needs to sort the values on the left and right.

Why It Matters

Fast in Practice

Quick sort is often one of the fastest comparison-based sorts in real implementations.

Strong Partition Mental Model

It teaches that one well-designed operation can create structure and simplify the rest of the problem.

Recursion Practice

Once learners understand partition, recursion becomes a natural “repeat on smaller parts” process.

Good Contrast

Quick sort provides a useful comparison with merge sort, which also uses divide and conquer but organizes the work differently.

Pseudocode

This version uses the Lomuto partition scheme, where the pivot is the last element of the current subarray:

QUICK-SORT(A, low, high):
    if low < high:
        p = PARTITION(A, low, high)
        QUICK-SORT(A, low, p - 1)
        QUICK-SORT(A, p + 1, high)

PARTITION(A, low, high):
    pivot = A[high]
    i = low - 1

    for j = low to high - 1:
        if A[j] <= pivot:
            i = i + 1
            swap A[i], A[j]

    swap A[i + 1], A[high]
    return i + 1

The important detail is that partition returns the pivot’s final index. Then quick sort only recurses on the two sides around it.

Complexity

Time Complexity

Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n²)

Space & Stability

Extra space: O(log n) average recursion stack
In-place partitioning: Yes
Stable: No

Quick sort performs best when partitions stay reasonably balanced. Poor pivots can make recursion unbalanced and increase the running time.

Common Mistakes

Thinking Swaps Are Random

They are not random. Each swap is part of building the correct left and right regions relative to the pivot.

Losing Track of the Pivot

The pivot is the reference point for partition. If learners lose the pivot, the whole process feels confusing.

Assuming the Pivot Moves Again Later

Once partition finishes, the pivot is in its final sorted position and is never processed again.

Recursing on the Whole Array Again

Quick sort only recurses on the subarrays to the left and right of the pivot, not the whole array.

Outcome

After this lesson, learners should be able to explain the role of the pivot, describe what partition guarantees, trace how recursion works on the left and right subarrays, and read the core quick sort pseudocode correctly.

Back to Home