Quick Sort

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 4 Time to complete: ~25 minutes

Table of Contents

1. Divide and Conquer, Different Split
2. The Partition Step (Lomuto Scheme)
3. Full Implementation
4. Average Case: O(n log n)
5. Worst Case: O(n²) and How Pivots Cause It
6. Pivot Selection Strategies
7. In-Place, But Not Stable
8. Summary & Next Steps

1. Divide and Conquer, Different Split

Quick sort is also divide-and-conquer (Chapter 4), but it splits differently: instead of splitting the array exactly in half, it picks a pivot element and partitions everything else into "smaller than pivot" and "larger than pivot" groups. The pivot itself ends up in its final sorted position after just one partition step — no merge step is needed afterward.

2. The Partition Step (Lomuto Scheme)

def partition(items, low, high):
    pivot = items[high]           # choose the last element as the pivot
    i = low - 1                    # boundary of "smaller than pivot" region
 
    for j in range(low, high):
        if items[j] <= pivot:
            i += 1
            items[i], items[j] = items[j], items[i]
 
    items[i + 1], items[high] = items[high], items[i + 1]   # place pivot correctly
    return i + 1                    # pivot's final index

Partitioning [5, 2, 8, 1, 9] with pivot = 9 (last element):
  Every element is ≤ 9, so they all move left of the boundary — pivot stays put.
  Result: [5, 2, 8, 1, 9], pivot index = 4

Partitioning [5, 2, 8, 1, 3] with pivot = 3 (last element):
  5 > 3: skip
  2 ≤ 3: swap into position → [2, 5, 8, 1, 3], i=0
  8 > 3: skip
  1 ≤ 3: swap into position → [2, 1, 8, 5, 3], i=1
  place pivot at i+1=2 → [2, 1, 3, 5, 8]
  Result: pivot (3) is now at index 2, with everything smaller to its left
          and everything larger to its right

3. Full Implementation

def quick_sort(items, low=0, high=None):
    if high is None:
        high = len(items) - 1
 
    if low < high:
        pivot_index = partition(items, low, high)
        quick_sort(items, low, pivot_index - 1)      # sort left of pivot
        quick_sort(items, pivot_index + 1, high)       # sort right of pivot
 
    return items

4. Average Case: O(n log n)

When the pivot lands roughly in the middle of the range each time, the array splits into two similarly-sized halves — the same log n levels of splitting as merge sort, with O(n) total partitioning work per level, giving O(n log n) on average. Unlike merge sort, this happens in place, with no extra array needed for merging.

5. Worst Case: O(n²) and How Pivots Cause It

If the pivot is consistently the smallest or largest remaining element — which happens with this simple "last element" pivot choice on already-sorted or reverse-sorted input — each partition step only shrinks the problem by one element instead of splitting it in half:

Already-sorted [1, 2, 3, 4, 5], always picking the LAST element as pivot:
  Partition: pivot=5, everything else is smaller → splits into [1,2,3,4] and []
  Partition: pivot=4, everything else is smaller → splits into [1,2,3] and []
  Partition: pivot=3, everything else is smaller → splits into [1,2] and []
  ... n levels of recursion, each doing O(n) partition work → O(n²) total

This is exactly the worst case flagged back in Module 1, Chapter 5 — a poor pivot strategy turns quick sort's O(n log n) into O(n²) on an input pattern (already-sorted or reverse-sorted data) that shows up constantly in real-world data.

6. Pivot Selection Strategies

In practice, production implementations use randomized or median-of-three pivots specifically to avoid the pathological case above.

7. In-Place, But Not Stable

Quick sort sorts in place — O(log n) space on average for the recursion stack, but no extra array like merge sort needs. However, it is not stable: the partition step can swap an element past another equal element, disrupting their original relative order. If stability matters, prefer merge sort (Chapter 4) or Python's built-in sort (Chapter 6).

8. Summary & Next Steps

Key Takeaways

• Quick sort partitions around a pivot so everything smaller ends up on one side and everything larger on the other, placing the pivot in its final position in one pass.
• Average case is O(n log n), in place — no extra array needed, unlike merge sort.
• Worst case is O(n²), triggered when the pivot is repeatedly the smallest/largest element — notably on already-sorted or reverse-sorted input with a naive pivot choice.
• Randomized or median-of-three pivot selection makes the worst case practically avoidable.
• Quick sort is in-place but not stable.

Concept Check

1. What does the partition step guarantee about the pivot's position once it completes?
2. Why does already-sorted input trigger quick sort's worst case when the pivot is always the last element?
3. Why does randomizing the pivot choice help avoid the worst case, without changing the algorithm's average-case complexity?

Next Chapter

→ Chapter 6: Choosing the Right Algorithm

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index