Introduction to Algorithms

Lecture 4: Quicksort

Prof. Charles E. Leiserson and Prof. Erik Demaine

Massachusetts Institute of Technology

August 19, 2025

Introduction to Algorithms: L4 Quicksort 1 / 56

Introduction to Algorithms

Content has been extracted from Introduction to Algorithms, Fourth Edition, by Cormen,
Leiserson, Rivest, and Stein. MIT Press. 2022.
Visit [Link]
Original slides from Introduction to Algorithms 6.046J/18.401J, Fall 2005 Class by Prof. Charles
Leiserson and Prof. Erik Demaine. MIT OpenCourseWare Initiative available at
[Link]

Introduction to Algorithms: L4 Quicksort 2 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 3 / 56

Quicksort

▶ Proposed by C.A.R. Hoare in 1962.

Introduction to Algorithms: L4 Quicksort 4 / 56

Quicksort

▶ Proposed by C.A.R. Hoare in 1962.

▶ Divide-and-conquer algorithm.

Introduction to Algorithms: L4 Quicksort 4 / 56

Quicksort

▶ Proposed by C.A.R. Hoare in 1962.

▶ Divide-and-conquer algorithm.
▶ Sorts ‘in place’ (like insertion sort, but not like merge sort).

Introduction to Algorithms: L4 Quicksort 4 / 56

Quicksort

▶ Proposed by C.A.R. Hoare in 1962.

▶ Divide-and-conquer algorithm.
▶ Sorts ‘in place’ (like insertion sort, but not like merge sort).
▶ Very practical (with tuning).

Introduction to Algorithms: L4 Quicksort 4 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 5 / 56

Divide and Conquer

Quicksort an n-element array:

1. Divide: Partition the array into two subarrays around a
pivot x such that elements in lower subarray ≤ x ≤
elements in upper subarray.

Introduction to Algorithms: L4 Quicksort 6 / 56

Divide and Conquer

Quicksort an n-element array:

1. Divide: Partition the array into two subarrays around a
pivot x such that elements in lower subarray ≤ x ≤
elements in upper subarray.
≤ x x > x

Introduction to Algorithms: L4 Quicksort 6 / 56

Divide and Conquer

Quicksort an n-element array:

1. Divide: Partition the array into two subarrays around a
pivot x such that elements in lower subarray ≤ x ≤
elements in upper subarray.
≤ x x > x
2. Conquer: Recursively sort the two subarrays.

Introduction to Algorithms: L4 Quicksort 6 / 56

Divide and Conquer

Quicksort an n-element array:

1. Divide: Partition the array into two subarrays around a
pivot x such that elements in lower subarray ≤ x ≤
elements in upper subarray.
≤ x x > x
2. Conquer: Recursively sort the two subarrays.
3. Combine: Trivial.

Introduction to Algorithms: L4 Quicksort 6 / 56

Divide and Conquer

Quicksort an n-element array:

1. Divide: Partition the array into two subarrays around a
pivot x such that elements in lower subarray ≤ x ≤
elements in upper subarray.
≤ x x > x
2. Conquer: Recursively sort the two subarrays.
3. Combine: Trivial.
Key:
Linear-time partitioning subroutine.

Introduction to Algorithms: L4 Quicksort 6 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 7 / 56

Partitioning Subroutine
1: procedure Partition(A, p, r)
2: x ← A[r]
3: i←p−1
4: for j ← p to r − 1 do
5: if A[j] ≤ x then
6: i←i+1
7: exchange A[i] ↔ A[j]
8: end if
9: end for
10: exchange A[i + 1] ↔ A[r]
11: return i + 1
12: end procedure

Introduction to Algorithms: L4 Quicksort 8 / 56

Partitioning Subroutine
1: procedure Partition(A, p, r) Running time:
2: x ← A[r] O(n) for n elements.
3: i←p−1
4: for j ← p to r − 1 do
5: if A[j] ≤ x then
6: i←i+1
7: exchange A[i] ↔ A[j]
8: end if
9: end for
10: exchange A[i + 1] ↔ A[r]
11: return i + 1
12: end procedure

Introduction to Algorithms: L4 Quicksort 8 / 56

Partitioning Subroutine
1: procedure Partition(A, p, r) Running time:
2: x ← A[r] O(n) for n elements.
3: i←p−1
4: for j ← p to r − 1 do
5: if A[j] ≤ x then
6: i←i+1
7: exchange A[i] ↔ A[j]
8: end if
9: end for
10: exchange A[i + 1] ↔ A[r]
11: return i + 1
12: end procedure

Invariants:
≤ x > x ? x
p i j r
Introduction to Algorithms: L4 Quicksort 8 / 56
Loop Invariants: Definition

≤ x > x ? x
p i j r

At the beginning of each iteration of the loop (lines 4–9), for

any array index k:
1. Low side: If p ≤ k ≤ i, then A[k] ≤ x.
2. High side: If i + 1 ≤ k ≤ j − 1, then A[k] ≥ x.
3. Pivot: If k = r, then A[k] = x.
These conditions define the partitioning into three regions:
▶ Elements ≤ x (low side).
▶ Elements > x (high side).
▶ The pivot element.

Introduction to Algorithms: L4 Quicksort 9 / 56

Initialization and Maintenance

Initialization:
▶ Before first iteration: i = p − 1, j = p.
▶ No values yet examined, so invariants hold trivially.
▶ Line 2 ensures pivot condition (3) holds.
Maintenance:
▶ If A[j] > x: only increment j, preserving high side property.
▶ If A[j] ≤ x: increment i, swap A[i] and A[j], then
increment j.
▶ Swapping ensures A[i] ≤ x and A[i + 1] . . . A[j − 1] > x.

Introduction to Algorithms: L4 Quicksort 10 / 56

Termination and Correctness

Termination:
▶ Loop ends when j = r.
▶ The unexamined subarray A[j . . . r − 1] is empty.
▶ All entries are in one of the three invariant regions.
Correctness:
▶ Array is partitioned into:
1. Elements ≤ x (low side).
2. Elements > x (high side).
▶ Pivot is placed immediately after the low side.

Introduction to Algorithms: L4 Quicksort 11 / 56

Regions in the Partition Procedure

Chapter 7 Quicksort

p i j r
x

≤x >x unknown

Figure 7.2 The four regions maintained by the procedure P ARTITIO

tan values in AŒp W i � are all less than or equal to x , the blue values in A
than x , the white values in AŒj W r  1� have unknown relationships to

p i j r
(a)
Introduction to Algorithms: L4 Quicksort >x x / 56
12
 tan values in AŒp W i � are all less than or equal to x , the blue values in AŒi C 1 j
W  1�
Handling x , the white
thanCases values in AŒj
During r 1� have unknown relationships to x , and AŒr � x
Partition W  D

p i j r
(a) >x x

≤x >x

p i j r
x

≤x >x

p i j r
(b) ≤x x

≤x >x

p i j r
x

≤x >x

Introduction to Algorithms: L4 Quicksort 13 / 56

 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
 7.1 Description of quicksort
Example of partitioning
i p,j r
(a) 2 8 7 1 3 5 6 4

p,i j r
(b) 2 8 7 1 3 5 6 4

p,i j r
(c) 2 8 7 1 3 5 6 4

p,i j r
(d) 2 8 7 1 3 5 6 4

p i j r
(e) 2 1 7 8 3 5 6 4

p i j r
(f) 2 1 3 8 7 5 6 4

p i j r
(g) 2 1 3 8 7 5 6 4

p i r
(h) 2 1 3 8 7 5 6 4

p i r
(i) 2 1 3 4 7 5 6 8
Introduction to Algorithms: L4 Quicksort 14 / 56
Pseudocode for Quicksort

1: procedure Quicksort(A, p, r)
2: if p < r then
3: q ← Partition(A,p, r)
4: Quicksort(A, p, q − 1)
5: Quicksort(A, q + 1, r)
6: end if
7: end procedure

Introduction to Algorithms: L4 Quicksort 15 / 56

Pseudocode for Quicksort

1: procedure Quicksort(A, p, r)
2: if p < r then
3: q ← Partition(A,p, r)
4: Quicksort(A, p, q − 1)
5: Quicksort(A, q + 1, r)
6: end if
7: end procedure

Initial call:
Quicksort(A, 1, n)

Introduction to Algorithms: L4 Quicksort 15 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 16 / 56

Performance of Quicksort

▶ Assume all input elements are distinct.

Introduction to Algorithms: L4 Quicksort 17 / 56

Performance of Quicksort

▶ Assume all input elements are distinct.

▶ In practice, there are better partitioning algorithms for
when duplicate input elements may exist.

Introduction to Algorithms: L4 Quicksort 17 / 56

Performance of Quicksort

▶ Assume all input elements are distinct.

▶ In practice, there are better partitioning algorithms for
when duplicate input elements may exist.
▶ Let T (n) = worst-case running time on an array of n
elements.

Introduction to Algorithms: L4 Quicksort 17 / 56

Worst-case of Quicksort

▶ Input sorted or reverse sorted.

Introduction to Algorithms: L4 Quicksort 18 / 56

Worst-case of Quicksort

▶ Input sorted or reverse sorted.

▶ Partition around min or max element.

Introduction to Algorithms: L4 Quicksort 18 / 56

Worst-case of Quicksort

▶ Input sorted or reverse sorted.

▶ Partition around min or max element.
▶ One side of partition always has no elements.

Introduction to Algorithms: L4 Quicksort 18 / 56

Worst-case of Quicksort

▶ Input sorted or reverse sorted.

▶ Partition around min or max element.
▶ One side of partition always has no elements.
T (n) =T (0) + T (n − 1) + Θ(n)
=Θ(1) + T (n − 1) + Θ(n)
=T (n − 1) + Θ(n)
=Θ(n2 )

Introduction to Algorithms: L4 Quicksort 18 / 56

Worst-case of Quicksort

▶ Input sorted or reverse sorted.

▶ Partition around min or max element.
▶ One side of partition always has no elements.
T (n) =T (0) + T (n − 1) + Θ(n)
=Θ(1) + T (n − 1) + Θ(n)
=T (n − 1) + Θ(n)
=Θ(n2 )
Arithmetic Series!

Introduction to Algorithms: L4 Quicksort 18 / 56

Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.20
Introduction to Algorithms: L4 Quicksort 19 / 56
Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn
T(n)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.21
Introduction to Algorithms: L4 Quicksort 20 / 56
Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn
cn
T(0) T(n–1)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.22
Introduction to Algorithms: L4 Quicksort 21 / 56
Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn
cn
T(0) c(n–1)
T(0) T(n–2)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.23
Introduction to Algorithms: L4 Quicksort 22 / 56
Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn
cn
T(0) c(n–1)
T(0) c(n–2)
T(0) O

Θ(1)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.24
Introduction to Algorithms: L4 Quicksort 23 / 56
Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn
cn ⎛ n ⎞
T(0) c(n–1) Θ⎜⎜ ∑ k ⎟⎟ = Θ(n 2 )
⎝ k =1 ⎠
T(0) c(n–2)
T(0) O

Θ(1)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.25
Introduction to Algorithms: L4 Quicksort 24 / 56
Worst-case Recursion Tree

Worst-case recursion tree

T (n) =T (0) + T (n − 1) + cn
T(n) = T(0) + T(n–1) + cn
cn ⎛ n ⎞
Θ(1) c(n–1) Θ⎜⎜ ∑ k ⎟⎟ = Θ(n 2 )
⎝ k =1 ⎠
Θ(1) c(n–2)
h=n T(n) = Θ(n) + Θ(n2)
Θ(1) O = Θ(n2)

Θ(1)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.26
Introduction to Algorithms: L4 Quicksort 25 / 56
Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 26 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

Introduction to Algorithms: L4 Quicksort 27 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

n
T (n) =2T + Θ(n)
2
=Θ(n lg n)

Introduction to Algorithms: L4 Quicksort 27 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

n
T (n) =2T + Θ(n)
2
=Θ(n lg n)

▶ Same as merge-sort.

Introduction to Algorithms: L4 Quicksort 27 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

n
T (n) =2T + Θ(n)
2
=Θ(n lg n)

▶ Same as merge-sort.
▶ Which case is this?

Introduction to Algorithms: L4 Quicksort 27 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

n
T (n) =2T + Θ(n)
2
=Θ(n lg n)

▶ Same as merge-sort.
▶ Which case is this? Case 2.

Introduction to Algorithms: L4 Quicksort 27 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

n
T (n) =2T + Θ(n)
2
=Θ(n lg n)

▶ Same as merge-sort.
▶ Which case is this? Case 2.
1 9
What if the split is always 10 : 10 ?

Introduction to Algorithms: L4 Quicksort 27 / 56

Best-case Performance
For intuition only!

If we’re lucky, Partition splits the array evenly:

n
T (n) =2T + Θ(n)
2
=Θ(n lg n)

▶ Same as merge-sort.
▶ Which case is this? Case 2.
1 9
What if the split is always 10 : 10 ?
   
1 9
T (n) =T n +T n + Θ(n)
10 10

What is the solution to this recurrence?

Introduction to Algorithms: L4 Quicksort 27 / 56

Performance of “Almost-best” Case
Analysis of “almost-best” case
T (n)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.28

Introduction to Algorithms: L4 Quicksort 28 / 56

Performance of “Almost-best” Case
Analysis of “almost-best” case
cn
T (101 n ) T (109 n )

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.29

Introduction to Algorithms: L4 Quicksort 29 / 56

Performance of “Almost-best” Case
Analysis of “almost-best” case
cn
1
10
cn 9
10
cn

T (100
1
n ) T (100
9
n ) T (100
9
n )T (100
81
n)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.30

Introduction to Algorithms: L4 Quicksort 30 / 56

Performance of “Almost-best” Case
Analysis of “almost-best” case
cn cn
1
10
cn 9
10
cn cn
log10/9n
1
100
cn 9
100
cn 9
100
cn 100 cn
81
cn
…

…
Θ(1) O(n)
O(n) leaves
leaves
Θ(1)

September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.31

Introduction to Algorithms: L4 Quicksort 31 / 56

Performance of “Almost-best” Case
Analysis of “almost-best” case
cn cn
1
10
cn 9
cn cn
log10n 10
log10/9n
1
100
cn 9
100
cn 9
100
cn 100 cn
81
cn
…

…
Θ(1) O(n)
O(n) leaves
leaves
Θ(n lg n) Θ(1)
Lucky! cn log10n ≤ T(n) ≤ cn log10/9n + Ο(n)
September 21, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L4.32

Introduction to Algorithms: L4 Quicksort 32 / 56

More Intuition

Suppose we alternate lucky, unlucky, lucky, unlucky, lucky, ...

n
L(n) =2U + Θ(n) lucky
2
U (n) =L (n − 1) + Θ(n) unlucky

Solving:
 n  n 
L(n) =2 L − 1 + Θ( ) + Θ(n)
n 2  2
=2L − 1 + Θ(n)
2
=Θ(n lg n) Lucky!

How can we make sure we are usually lucky?

Introduction to Algorithms: L4 Quicksort 33 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 34 / 56

Randomized Quicksort

Idea:
Partition around a random element.
▶ Running time is independent of the input order.
▶ No assumptions need to be made about the input
distribution.
▶ No specific input elicits the worst-case behavior.
▶ The worst case is determined only by the output of a
random-number generator.

Introduction to Algorithms: L4 Quicksort 35 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 36 / 56

Randomized Quicksort Analysis

Let T (n) = the random variable for the running time of

randomized quicksort on an input of size n, assuming random
numbers are independent.

For k = 0, 1, . . . , n − 1, define the indicator random variable.


1 if Partition generates a k : n − k − 1 split,
Xk =
0 otherwise.

Introduction to Algorithms: L4 Quicksort 37 / 56

Randomized Quicksort Analysis

Let T (n) = the random variable for the running time of

randomized quicksort on an input of size n, assuming random
numbers are independent.

For k = 0, 1, . . . , n − 1, define the indicator random variable.


1 if Partition generates a k : n − k − 1 split,
Xk =
0 otherwise.

E[Xk ] = 0 · P r{Xk = 0} + 1 · P r{Xk = 1} = P r{Xk = 1} = n1 ,

since all splits are equally likely, assuming element are distinct.

Introduction to Algorithms: L4 Quicksort 37 / 56

Analysis (Cont.)



 T (0) + T (n − 1) + Θ(n) if 0 : n − 1 split,
 T (1) + T (n − 2) + Θ(n) if 1 : n − 2 split,

T (n) = ..


 .
T (n − 1) + T (0) + Θ(n) if n − 1 : 0 split.


n−1
P
= Xk (T (k) + T (n − k − 1) + Θ(n))
k=0

Introduction to Algorithms: L4 Quicksort 38 / 56

Plan

Description of Quicksort

Divide & Conquer

Partitioning

Worst-case Analysis

Intuition

Randomized Quicksort

Analysis

Expected Running Time

Introduction to Algorithms: L4 Quicksort 39 / 56

Calculating expectation
Take expectations of both sides.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0

Introduction to Algorithms: L4 Quicksort 40 / 56

Calculating expectation
Linearity of expectation.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0

Introduction to Algorithms: L4 Quicksort 41 / 56

Calculating expectation
Independence of Xk from other random choices.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0
n−1
X
= E[Xk ] · E[T (k) + T (n − k − 1) + Θ(n)]
k=0

Introduction to Algorithms: L4 Quicksort 42 / 56

Calculating expectation
1
E[Xk ] = n
.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0
n−1
X
= E[Xk ] · E[T (k) + T (n − k − 1) + Θ(n)]
k=0
n−1
1 X
= E[T (k) + T (n − k − 1) + Θ(n)]
n
k=0

Introduction to Algorithms: L4 Quicksort 43 / 56

Calculating expectation
Linearity of expectation.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0
n−1
X
= E[Xk ] · E[T (k) + T (n − k − 1) + Θ(n)]
k=0
n−1 n−1 n−1
1 X 1X 1X
= E[T (k)] + E[T (n − k − 1)] + Θ(n)
n n n
k=0 k=0 k=0

Introduction to Algorithms: L4 Quicksort 44 / 56

Calculating expectation
Summations have identical terms.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0
n−1
X
= E[Xk ] · E[T (k) + T (n − k − 1) + Θ(n)]
k=0
n−1 n−1 n−1
1 X 1X 1X
= E[T (k)] + E[T (n − k − 1)] + Θ(n)
n n n
k=0 k=0 k=0
n−1 n−1
2 X 1 X
= E[T (k)] + Θ(n)
n n
k=0 k=0

Introduction to Algorithms: L4 Quicksort 45 / 56

Calculating expectation
n · Θ(n) = Θ(n2 ).

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0
n−1
X
= E[Xk ] · E[T (k) + T (n − k − 1) + Θ(n)]
k=0
n−1 n−1 n−1
1 X 1X 1X
= E[T (k)] + E[T (n − k − 1)] + Θ(n)
n n n
k=0 k=0 k=0
n−1
2 X 1
= E[T (k)] + Θ(n2 )
n n
k=0

Introduction to Algorithms: L4 Quicksort 46 / 56

Calculating expectation
Sum up.

"n−1 #
X
E[T (n)] = E Xk (T (k) + T (n − k − 1) + Θ(n))
k=0
n−1
X
= E [Xk (T (k) + T (n − k − 1) + Θ(n))]
k=0
n−1
X
= E[Xk ] · E[T (k) + T (n − k − 1) + Θ(n)]
k=0
n−1 n−1 n−1
1 X 1X 1X
= E[T (k)] + E[T (n − k − 1)] + Θ(n)
n n n
k=0 k=0 k=0
n−1
2 X
= E[T (k)] + Θ(n)
n
k=0

Introduction to Algorithms: L4 Quicksort 47 / 56

Hairy recurrence

n−1
2X
E[T (n)] = E[T (k)] + Θ(n)
n
k=2

(The k = 0, 1 terms can be absorbed in the Θ(n).)

Prove:
E[T (n)] ≤ an lg n for constant a > 0.
▶ Choose a large enough so that an lg n dominates E[T (n)]
for sufficiently small n ≥ 2.

Use fact:
n−1
k lg k ≤ 12 n2 lg n − 18 n2 (exercise).
P
k=2

Introduction to Algorithms: L4 Quicksort 48 / 56

Substitution method
Substitute inductive hypothesis.

n−1
2X
E[T (n)] ≤ ak lg k + Θ(n)
n
k=2

Introduction to Algorithms: L4 Quicksort 49 / 56

Substitution method
Use fact.

n−1
2X
E[T (n)] ≤ ak lg k + Θ(n)
n
k=2
 
2a 1 2 1
≤ n lg n − n2 + Θ(n)
n 2 8

Introduction to Algorithms: L4 Quicksort 50 / 56

Substitution method

n−1
2X
E[T (n)] ≤ ak lg k + Θ(n)
n
k=2
 
2a 1 2 1 2
≤ n lg n − n + Θ(n)
n 2 8
 an 
= an lg n − − Θ(n)
4
≤ an lg n,
if a is chosen large enough so that
an
dominates the Θ(n).
4

Introduction to Algorithms: L4 Quicksort 51 / 56

Quicksort in practice

▶ Quicksort is a great general-purpose sorting algorithm.

Introduction to Algorithms: L4 Quicksort 52 / 56

Quicksort in practice

▶ Quicksort is a great general-purpose sorting algorithm.

▶ Quicksort is typically over twice as fast as merge sort.

Introduction to Algorithms: L4 Quicksort 52 / 56

Quicksort in practice

▶ Quicksort is a great general-purpose sorting algorithm.

▶ Quicksort is typically over twice as fast as merge sort.
▶ Quicksort can benefit substantially from code tuning.

Introduction to Algorithms: L4 Quicksort 52 / 56

Quicksort in practice

▶ Quicksort is a great general-purpose sorting algorithm.

▶ Quicksort is typically over twice as fast as merge sort.
▶ Quicksort can benefit substantially from code tuning.
▶ Quicksort behaves well even with caching and virtual
memory.

Introduction to Algorithms: L4 Quicksort 52 / 56

 End of Lecture 4.

Introduction to Algorithms: L4 Quicksort 53 / 56

TDT5FTOTC

Introduction to Algorithms: L4 Quicksort 54 / 56

Top 5 Fundamental Takeaways

Introduction to Algorithms: L4 Quicksort 55 / 56

Top 5 Fundamental Takeaways
5 Quicksort is a Divide-and-Conquer Algorithm – It
recursively partitions an array around a pivot and sorts the
subarrays efficiently.

Introduction to Algorithms: L4 Quicksort 55 / 56

Top 5 Fundamental Takeaways
5 Quicksort is a Divide-and-Conquer Algorithm – It
recursively partitions an array around a pivot and sorts the
subarrays efficiently.
4 Partitioning is the Core of Quicksort – The partitioning
step ensures elements are correctly placed around the pivot in
O(n) time.

Introduction to Algorithms: L4 Quicksort 55 / 56

Top 5 Fundamental Takeaways
5 Quicksort is a Divide-and-Conquer Algorithm – It
recursively partitions an array around a pivot and sorts the
subarrays efficiently.
4 Partitioning is the Core of Quicksort – The partitioning
step ensures elements are correctly placed around the pivot in
O(n) time.
3 Best-case and Worst-case Analysis – Quicksort runs in
O(n log n) in the best case but can degrade to O(n2 ) if poorly
partitioned.

Introduction to Algorithms: L4 Quicksort 55 / 56

Top 5 Fundamental Takeaways
5 Quicksort is a Divide-and-Conquer Algorithm – It
recursively partitions an array around a pivot and sorts the
subarrays efficiently.
4 Partitioning is the Core of Quicksort – The partitioning
step ensures elements are correctly placed around the pivot in
O(n) time.
3 Best-case and Worst-case Analysis – Quicksort runs in
O(n log n) in the best case but can degrade to O(n2 ) if poorly
partitioned.
2 Randomized Quicksort Helps Avoid Worst-case
Behavior – Choosing a random pivot prevents consistently bad
splits and ensures an expected O(n log n) runtime.

Introduction to Algorithms: L4 Quicksort 55 / 56

Top 5 Fundamental Takeaways
5 Quicksort is a Divide-and-Conquer Algorithm – It
recursively partitions an array around a pivot and sorts the
subarrays efficiently.
4 Partitioning is the Core of Quicksort – The partitioning
step ensures elements are correctly placed around the pivot in
O(n) time.
3 Best-case and Worst-case Analysis – Quicksort runs in
O(n log n) in the best case but can degrade to O(n2 ) if poorly
partitioned.
2 Randomized Quicksort Helps Avoid Worst-case
Behavior – Choosing a random pivot prevents consistently bad
splits and ensures an expected O(n log n) runtime.
1 Quicksort is Highly Efficient in Practice – It outperforms
merge sort in most cases and benefits from hardware
optimizations.

Introduction to Algorithms: L4 Quicksort 55 / 56

Introduction to Algorithms

Content has been extracted from Introduction to Algorithms, Fourth Edition, by Cormen,
Leiserson, Rivest, and Stein. MIT Press. 2022.
Visit [Link]
Original slides from Introduction to Algorithms 6.046J/18.401J, Fall 2005 Class by Prof. Charles
Leiserson and Prof. Erik Demaine. MIT OpenCourseWare Initiative available at
[Link]

Introduction to Algorithms: L4 Quicksort 56 / 56