Skip to content

Volume ITechnology

4.0.28 — Quick Sort ​

Classic · Medium · LeetCode 912 (Sort an Array), LeetCode 215 (Kth Largest, via quickselect)

The problem ​

Sort a list in place, in increasing order, without sort().

[10, 80, 30, 90, 40, 50, 70]  →  [10, 30, 40, 50, 70, 80, 90]

Where it comes from ​

In 1959, a 25-year-old British student named Tony Hoare was in Moscow, working on a program to translate Russian into English. He needed to sort the words of each sentence so he could look them up in a dictionary stored on magnetic tape. Insertion sort was too slow. He invented quicksort, and published it in 1961. Hoare later won the Turing Award, computing's highest prize. Sixty years on, variations of his idea still sort most of the world's data.

The idea ​

Merge sort does nothing clever when it splits and does all its work when it merges. Quicksort does the opposite. It does all its work when it splits, so that no merging is needed at all.

  1. Pick one element, called the pivot.
  2. Rearrange the list so that everything smaller than the pivot is on its left, and everything bigger is on its right. This step is called partitioning. The pivot is now in its final, sorted position. It never moves again.
  3. Sort the left part and the right part the same way.

Why is no merge needed? After partitioning, every value on the left is smaller than every value on the right. So once each side is sorted, the whole list is sorted, just by sitting next to each other.

Partitioning, step by step ​

This version is called the Lomuto partition, after Nico Lomuto, who popularised it. It is the easiest to get right. Take the last element as the pivot. Walk through the rest with j. Keep a boundary i. Everything to the left of i is smaller than the pivot.

smaller than pivotpivot or biggernot looked at yetpivot↑ i↑ jlohi
The four regions during a Lomuto partition. j looks at one new value each step. If it is smaller than the pivot, it is swapped to position i, and the green region grows by one. At the end, the pivot is swapped into position i, between the two regions.

When j finds a value smaller than the pivot, swap it into position i and move i forward. That grows the green region. When j finds a value that is not smaller, do nothing. It simply stays in the red region. At the end, swap the pivot into position i. Everything before it is smaller, and everything after it is not.

The solution ​

python
def partition(nums: list[int], lo: int, hi: int) -> int:
    pivot = nums[hi]                          # (1)
    i = lo                                    # (2)
    for j in range(lo, hi):
        if nums[j] < pivot:                   # (3)
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[hi] = nums[hi], nums[i]     # (4)
    return i                                  # (5)

def quick_sort(nums: list[int], lo: int = 0, hi: int | None = None) -> None:
    if hi is None:
        hi = len(nums) - 1
    if lo >= hi:                              # (6)
        return
    p = partition(nums, lo, hi)
    quick_sort(nums, lo, p - 1)               # (7)
    quick_sort(nums, p + 1, hi)

a = [10, 80, 30, 90, 40, 50, 70]
quick_sort(a)
print(a)   # → [10, 30, 40, 50, 70, 80, 90]

(1) Use the last element of this range as the pivot.

(2) i is where the next small value will go. At the start, no small values have been found.

(3) A value smaller than the pivot. Swap it to the boundary and grow the small region.

(4) Put the pivot between the two regions. The value at i was the first "pivot or bigger" value, so it can safely move to the end.

(5) Return where the pivot landed. It is now in its final place.

(6) A range of zero or one element is already sorted. This is the base case.

(7) Sort each side. The pivot at p is left out of both, because it is already in place.

Trace of the first partition ​

On [10, 80, 30, 90, 40, 50, 70], pivot 70:

jnums[j]smaller than 70?actionlist afteri
010yesswap with itself10 80 30 90 40 50 701
180nonone10 80 30 90 40 50 701
230yesswap 80 ↔ 3010 30 80 90 40 50 702
390nonone10 30 80 90 40 50 702
440yesswap 80 ↔ 4010 30 40 90 80 50 703
550yesswap 90 ↔ 5010 30 40 50 80 90 704
endpivot 70 ↔ 8010 30 40 50 70 90 80

The 70 is now at index 4, its final place. Left of it: 10, 30, 40, 50, all smaller. Right of it: 90, 80, both bigger. Quicksort now sorts [10, 30, 40, 50] and [90, 80] separately.

Complexity, worked out ​

The good case. If every pivot lands near the middle, each partition splits its range roughly in half. That is the same shape as merge sort: about \log_2 n levels, and the partitions on each level together touch all n elements. So O(n \log n).

The bad case. Now give it a list that is already sorted, and keep choosing the last element as the pivot. The last element is the largest. Everything else goes to its left, and nothing goes to its right. The range only shrinks by one each time.

(n - 1) + (n - 2) + \dots + 1 = \frac{n(n-1)}{2}

That is O(n^2), as slow as bubble sort. The recursion also goes n levels deep. In Python, sorting an already-sorted list of 2,000 elements this way crashes with RecursionError. This is the best-known weakness of quicksort. It matters a lot, because sorted or nearly sorted lists are very common in real life.

The average case. With a random list, or a random pivot, a pivot usually lands somewhere in the middle half. Even a lopsided split, like 25% and 75%, still gives O(\log n) levels. It just takes a few more of them. A careful calculation shows quicksort averages about 1.39\, n \log_2 n comparisons. That is O(n \log n).

The fix: a random pivot. Pick the pivot at random, and swap it to the end before partitioning. Now no particular input is bad. The worst case still exists, but it needs bad luck on almost every pick, which effectively never happens.

python
import random

def quick_sort_random(nums: list[int], lo: int = 0, hi: int | None = None) -> None:
    if hi is None:
        hi = len(nums) - 1
    while lo < hi:                                     # (1)
        r = random.randint(lo, hi)
        nums[r], nums[hi] = nums[hi], nums[r]          # (2)
        p = partition(nums, lo, hi)
        if p - lo < hi - p:                            # (3)
            quick_sort_random(nums, lo, p - 1)
            lo = p + 1
        else:
            quick_sort_random(nums, p + 1, hi)
            hi = p - 1

big = list(range(5000))
quick_sort_random(big)
print(big[:5], big[-1])   # → [0, 1, 2, 3, 4] 4999

(1) A loop takes the place of the second recursive call.

(2) Move a random element to the end, so partition uses it as the pivot.

(3) Recurse into the smaller side, and loop on the larger side. The smaller side is at most half the range, so the recursion is never more than \log_2 n deep, even with bad luck. This is how real libraries keep quicksort's stack small.

Memory. Partitioning swaps within the list, so quicksort is in place apart from its recursion stack: O(\log n) with the smaller-side trick.

CaseTime
BestO(n \log n)
AverageO(n \log n)
Worst (sorted input, last-element pivot)O(n^2)
Extra memoryO(\log n) stack
StableNo

Why is it called quick, if merge sort never has a bad case? ​

On average, quicksort beats merge sort in practice, often by a good margin. Three reasons:

  1. No extra list. Merge sort writes every element into a helper list on every level, then copies back. Quicksort only swaps inside the original list.
  2. It reads memory in order. j walks straight along the list. Processors are much faster at reading memory in order, because they load nearby values into a small fast memory called the cache before you ask for them.
  3. Its inner loop is tiny. One comparison, and sometimes one swap.

C++'s std::sort is a quicksort with safety nets. It switches to heap sort if the recursion gets too deep, and to insertion sort for small pieces. That mix is called introsort, and 4.10 describes it.

Two problems quicksort has, and their fixes ​

Many repeated values. If every element is the same, Lomuto puts everything on one side, and quicksort falls to O(n^2) again. The fix is a three-way partition: smaller, equal and bigger. The equal block is never touched again. That is exactly the Dutch national flag from 4.0.20, with "0, 1, 2" replaced by "less than, equal to, greater than the pivot".

It is not stable. A long-distance swap can jump an element over an equal one. If you need stability, use merge sort.

Quickselect: the k-th smallest without sorting ​

Partition puts the pivot in its final position. If you want the k-th smallest element and the pivot lands at position k, you are done. If it lands to the right of k, the answer is on the left. So only recurse into one side.

python
def quickselect(nums: list[int], k: int) -> int:
    """k-th smallest, counting from 0. Reorders nums."""
    lo, hi = 0, len(nums) - 1
    while True:
        r = random.randint(lo, hi)
        nums[r], nums[hi] = nums[hi], nums[r]
        p = partition(nums, lo, hi)
        if p == k:
            return nums[p]
        if p < k:
            lo = p + 1        # answer is to the right
        else:
            hi = p - 1        # answer is to the left

print(quickselect([7, 10, 4, 3, 20, 15], 2))   # → 7

On average, each step throws away about half of what is left. The work is n + n/2 + n/4 + \dots, which adds up to less than 2n. So quickselect is O(n) on average, which is faster than sorting. This solves "k-th largest element" in 4.17.4.

What the interviewer will push on ​

These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.

"What is the worst case, and what input causes it?"O(n^2). It happens on an already sorted list when the first or last element is always the pivot. Every split is then as uneven as possible.

"How do you avoid that?" Pick the pivot at random. For lists with many equal values, also use a three-way split: smaller, equal and bigger.

"Merge sort is never slow. Why is quicksort usually faster?" It needs no second list, it reads memory in order, and its inner loop is very small.

"How much extra memory does quicksort use?" About \log n for the recursive calls, if you always recurse into the smaller side first. Without that, it can be O(n) in the worst case.

"Is quicksort stable?" No.

"Find the k-th largest element in O(n) on average." Use quickselect. Partition once, then continue only on the side that holds the answer.

One thing to volunteer: "Merge sort splits simply and merges with care. Quicksort splits with care and needs no merge."

Next: 4.0.29 Heap Sort. O(n \log n) in the worst case and in place, by treating the list as a tree.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet