1 of 104

1

WARNING, THESE SLIDES HAVE NOT YET BEEN UPDATED FOR FALL 2026

2 of 104

2

What questions do you have about Fall 2026 classes?

yellkey.com/end

3 of 104

Insertion Sort and Quicksort

3

Lecture 33 (Sorting 2)

CS61B, Spring 2026 @ UC Berkeley

Josh Hug and Manuel Sabin

4 of 104

Naive Insertion Sort

Lecture 33, CS61B, Spring 2026

Insertion Sort

Naive Insertion Sort
In-Place Insertion Sort
Insertion Sort Runtime

Quicksort

Quicksort Backstory,�Partitioning
Quicksort

4

5 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

5

32

15

2

17

19

26

41

17

Input:

Output:

6 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

6

32

15

2

17

19

26

41

17

Input:

Output:

7 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

7

32

15

2

17

19

26

41

17

32

Input:

Output:

8 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

8

32

15

2

17

19

26

41

17

32

15

Input:

Output:

9 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

9

32

15

2

17

19

26

41

17

32

15

2

Input:

Output:

10 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

10

32

15

2

17

19

26

41

17

32

15

2

17

Input:

Output:

11 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

11

32

15

2

17

19

26

41

17

32

15

2

17

19

Input:

Output:

12 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

12

32

15

2

17

19

26

41

17

32

15

2

17

19

26

Input:

Output:

13 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

13

32

15

2

17

19

26

41

17

32

15

2

17

19

26

41

Input:

Output:

14 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

14

32

15

2

17

19

26

41

17

32

15

2

17

19

26

41

17

Input:

Output:

15 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

Naive approach, build entirely new output:

15

32

15

2

17

19

26

41

17

32

15

2

17

19

26

41

17

Input:

Output:

Can we eliminate this output array?

16 of 104

In-Place Insertion Sort

Lecture 33, CS61B, Spring 2026

Insertion Sort

Naive Insertion Sort
In-Place Insertion Sort
Insertion Sort Runtime

Quicksort

Quicksort Backstory,�Partitioning
Quicksort

16

17 of 104

Insertion Sort

General strategy:

Starting with an empty output sequence.
Add each item from input, inserting into output at right point.

For naive approach, if output sequence contains k items, worst cost to insert a single item is k.

Might need to move everything over.

More efficient method:

Do everything in place using swapping.

17

18 of 104

Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items

18

32

15

2

17

19

26

41

17

Input:

19 of 104

Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items

19

32

15

2

17

19

26

41

17

i

Input:

20 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items

20

32

15

2

17

19

26

41

17

i

sorted

unexamined

Input:

21 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items

21

32

15

2

17

19

26

41

17

i

sorted

unexamined

Input:

22 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

22

32

15

2

17

19

26

41

17

i

sorted

unexamined

Input:

23 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

23

15

32

2

17

19

26

41

17

i

unexamined

Input:

24 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

24

15

32

2

17

19

26

41

17

i

sorted

unexamined

Input:

25 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

25

15

32

2

17

19

26

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

26 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

26

15

2

32

17

19

26

41

17

i

j

Note: We’ve temporarily broken our invariant that the items up through item i should be sorted!

In example above: Use j pointer to track current spot of traveling item.

unexamined

Input:

27 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

27

2

15

32

17

19

26

41

17

i

j

Once the traveller settles, the invariant is restored.

unexamined

Input:

Use j pointer to track current spot of traveling item.

28 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

28

2

15

32

17

19

26

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

29 of 104

In-place Insertion Sort: yellkey.com/service

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

29

2

15

32

17

19

26

41

17

i

j

sorted

unexamined

Input:

current spot of traveling item

while (/* FILL ME IN */ ) {

// Swap backwards

}

30 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

30

2

15

32

17

19

26

41

17

i

j

sorted

unexamined

Input:

current spot of traveling item

while (j > 0 && input[j - 1] > input[j]) {

// Swap backwards

}

31 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

31

2

15

17

32

19

26

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

32 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

32

2

15

17

32

19

26

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

33 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

33

2

15

17

32

19

26

41

17

j

sorted

i

unexamined

Input:

Use j pointer to track current spot of traveling item.

34 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

34

2

15

17

19

32

26

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

35 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

35

2

15

17

19

32

26

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

36 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

36

2

15

17

19

32

26

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

37 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

37

2

15

17

19

26

32

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

38 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

38

2

15

17

19

26

32

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

39 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

39

2

15

17

19

26

32

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

40 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

40

2

15

17

19

26

32

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

41 of 104

In-place Insertion Sort: yellkey.com/impact

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

41

2

15

17

19

26

32

41

17

i

j

sorted

unexamined

Input:

How many swaps do we need to do to get 17 in the correct place?

current spot of traveling item

42 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

42

2

15

17

19

26

32

17

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

1 swap so far

43 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

43

2

15

17

19

26

17

32

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

2 swaps so far

44 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

44

2

15

17

19

17

26

32

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

3 swaps so far

45 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

45

2

15

17

19

26

32

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

4 swaps so far

46 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

46

2

15

17

19

26

32

41

17

i

j

unexamined

Input:

Use j pointer to track current spot of traveling item.

4 swaps total

47 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

47

2

15

17

19

26

32

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

48 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

48

2

15

17

19

26

32

41

17

i

j

sorted

unexamined

Input:

Use j pointer to track current spot of traveling item.

49 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

49

2

15

17

19

26

32

17

41

i

j

Input:

Use j pointer to track current spot of traveling item.

50 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

50

2

15

17

19

26

17

32

41

i

j

Input:

Use j pointer to track current spot of traveling item.

51 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

51

2

15

17

19

17

26

32

41

i

j

Input:

Use j pointer to track current spot of traveling item.

52 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

52

2

15

17

19

26

32

41

i

j

Input:

Use j pointer to track current spot of traveling item.

53 of 104

In-place Insertion Sort

General strategy:

Repeat for i = 0 to N - 1:

“Insert” item at index i into the right place among sorted items (traveller)

How? Swap item backwards until traveller is in the right place among all previously examined items.

53

2

15

17

19

26

32

41

Input:

i

j

sorted

Use j pointer to track current spot of traveling item.

54 of 104

In-place Insertion Sort: Reflections on Naming

54

2

15

17

19

26

32

41

Input:

i

j

sorted

From John Ousterhout’s Software Design Lecture

Use j pointer to track current spot of traveling item.

55 of 104

In-place Insertion Sort: Reflections on Naming: yellkey.com/love

What new names would you propose for i and j?

Should we take a more extreme step?

55

2

15

17

19

26

32

41

Input:

i

j

sorted

current spot of traveling item

56 of 104

In-place Insertion Sort: Reflections on Naming

What new names would you propose for i and j? Should we take a more extreme step?

Your ideas:

J -> travelerl i -> start
i: currentIndex
i: lastSortedIndex, j: traveler

56

2

15

17

19

26

32

41

Input:

i

j

sorted

current spot of traveling item

57 of 104

In-place Insertion Sort: Reflections on Naming

What new names would you propose for i and j? Should we take a more extreme step?

John Ousterhout’s suggestions:

Replace j with traveller
Awkward to even describe i; change to examined and change semantics to be one past i. Comment // Includes current traveller

Kay’s ideas:

Replace i with sorted_until or num_sorted

57

2

15

17

19

26

32

41

Input:

i

j

sorted

current spot of traveling item

58 of 104

Insertion Sort Runtime

Lecture 33, CS61B, Spring 2026

Insertion Sort

Naive Insertion Sort
In-Place Insertion Sort
Insertion Sort Runtime

Miscellaneous Sorts

Quicksort

Quicksort Backstory,�Partitioning
Quicksort

58

59 of 104

In-place Insertion Sort

Two more examples.

7 swaps:

36 swaps:

59

P O T A T O

P O T A T O (0 swaps)

O P T A T O (1 swap )

O P T A T O (0 swaps)

A O P T T O (3 swaps)

A O P T T O (0 swaps)

A O O P T T (3 swaps)

S O R T E X A M P L E

S O R T E X A M P L E (0 swaps)

O S R T E X A M P L E (1 swap )

O R S T E X A M P L E (1 swap )

O R S T E X A M P L E (0 swaps)

E O R S T X A M P L E (4 swaps)

E O R S T X A M P L E (0 swaps)

A E O R S T X M P L E (6 swaps)

A E M O R S T X P L E (5 swaps)

A E M O P R S T X L E (4 swaps)

A E L M O P R S T X E (7 swaps)

A E E L M O P R S T X (8 swaps)

Purple: Element that we’re moving left (with swaps).

Black: Elements that got swapped with purple.

Grey: Not considered this iteration.

60 of 104

Insertion Sort Runtime: yellkey.com/she

What is the best- and worst-case runtime of insertion sort?

Best: Θ(1), Worst: Θ(N)
Best: Θ(N), Worst: Θ(N)
Best: Θ(1), Worst: Θ(N²)
Best: Θ(N), Worst: Θ(N²)
Best: Θ(N²), Worst: Θ(N²)

36 swaps:

60

61 of 104

Insertion Sort Runtime

What is the best- and worst-case runtime of insertion sort?

Best: Θ(1), Worst: Θ(N)
Best: Θ(N), Worst: Θ(N)
Best: Θ(1), Worst: Θ(N²)
Best: Θ(N), Worst: Θ(N²)
Best: Θ(N²), Worst: Θ(N²)

36 swaps:

61

62 of 104

Picking the Best Sort: yellkey.com/notice

Suppose we do the following:

Start with a sorted array of 1,000,000 integers.
Select one integer randomly and change it.
Sort using algorithm X of your choice.

Which sorting algorithm would be the fastest choice for X?

Selection Sort: O(N²)
Heapsort: O(N Log N)
Mergesort: O(N Log N)
Insertion Sort: O(N²)

62

63 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

�What’s the worst case number of inversions?

(N-1) + (N-2) + … + 1 = N * (N - 1) / 2

63

2

15

17

19

26

17

32

41

17

64 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

64

19-17

(out of 36 inversions)

2

15

17

19

26

17

32

41

17

65 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

65

19-17, 19-17

(out of 36 inversions)

2

15

17

19

26

17

32

41

17

66 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

66

19-17, 19-17, 26-17

(out of 36 inversions)

2

15

17

19

26

17

32

41

17

67 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

67

19-17, 19-17, 26-17, 26-17

(out of 36 inversions)

2

15

17

19

26

17

32

41

17

68 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

68

19-17, 19-17, 26-17, 26-17

32-17

(out of 36 inversions)

2

15

17

19

26

17

32

41

17

69 of 104

Recall: Inversions

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

Given a sequence of elements with Z inversions.
Perform a sequence of operations that reduces inversions to 0.

69

19-17, 19-17, 26-17, 26-17

32-17, 41-17 = 6 total inversions

(out of 36 inversions)

2

15

17

19

26

17

32

41

17

70 of 104

Observation: Each swap in Insertion Sort reduces the number of inversions by 1

Inversions between red items don't change (because they don't move)

Inversions between a red and blue item don't change (their relative position in the array stays the same)

We fix one inversion within the blue items

So total number of inversions decrease by 1 every swap

70

2

15

17

19

26

17

32

41

17

i

j

2

15

17

19

17

26

32

41

17

i

j

71 of 104

Observation: Insertion Sort on Almost Sorted Arrays

For arrays that are almost sorted, insertion sort does very little work.

Left array: 5 inversions, so only 5 swaps.
Right array: 3 inversion, so only 3 swaps.

71

72 of 104

Picking the Best Sort: How many inversions?

Suppose we do the following:

Start with a sorted array of 1,000,000 integers.
Select one integer randomly and change it.
Sort using algorithm X of your choice.

What’s the worst-case number of inversions here?

Example shorter array: [9, 12, 25, 34, 55]

What one number would you change to introduce the most inversions?

72

73 of 104

Picking the Best Sort: How many inversions?

Suppose we do the following:

Start with a sorted array of 1,000,000 integers.
Select one integer randomly and change it.
Sort using algorithm X of your choice.

What’s the worst-case number of inversions here? N - 1

Example shorter array: [9, 12, 25, 34, 55]

What one number would you change to introduce the most inversions?

Change 9 to 56 (4 inversions; ever item after it)
Change 55 to 8 (inverted with every item before it)

73

74 of 104

Picking the Best Sort

Suppose we do the following:

Start with a sorted array of 1,000,000 integers.
Select one integer randomly and change it.
Sort using algorithm X of your choice.

In the worst case, we have N - 1 inversions (Θ(N) inversions)

Which sorting algorithm would be the fastest choice for X? Worst case run-times:

Selection Sort: O(N²)
Heapsort: O(N log N)
Mergesort: O(N log N)
Insertion Sort O(N²)

74

75 of 104

Picking the Best Sort

Suppose we do the following:

Start with a sorted array of 1,000,000 integers.
Select one integer randomly and change it.
Sort using algorithm X of your choice.

In the worst case, we have N - 1 inversions (Θ(N) inversions)

Which sorting algorithm would be the fastest choice for X? Run-times:

Selection Sort: Θ(N²)
Heapsort: O(N log N)
Mergesort: Θ(N log N)
Insertion Sort: O(N²) Θ(N)

75

Number of swaps = number of inversions!

76 of 104

Insertion Sort Sweet Spots

On arrays with a small number of inversions, insertion sort is extremely fast.

One exchange per inversion (and number of comparisons is similar). Runtime is Θ(N + K) where K is number of inversions.
K is on average Θ(N²) in random lists, but…
Define an almost sorted array as one in which number of inversions ≤ cN for some c. Insertion sort is excellent on these arrays.

Less obvious: For small arrays (N < 15 or so), insertion sort is fastest.

More of an empirical fact than a theoretical one.
Theoretical analysis beyond scope of the course.
Rough idea: Divide and conquer algorithms like heapsort / mergesort spend too much time dividing, but insertion sort goes straight to the conquest.
The Java implementation of Mergesort does this (Link).

76

77 of 104

Sorts So Far

77

See this link for bonus slides on Shell's Sort, an optimization of insertion sort.

	Best Case Runtime	Worst Case Runtime	Space	Notes
Selection Sort	Θ(N²) Find smallest item in remaining items, N times	Θ(N²)	Θ(1)
Heapsort (in place)	Θ(N)�All duplicates	Θ(N log N)	Θ(1)**	Bad cache (61C) performance.
Mergesort	Θ(N log N)	Θ(N log N)	Θ(N)	Faster than heapsort.
Insertion Sort�(in place)	Θ(N)�cN Inversions	Θ(N²)	Θ(1)	Best for small N or almost sorted.

78 of 104

Quicksort Backstory, Partitioning

Lecture 33, CS61B, Spring 2026

Insertion Sort

Naive Insertion Sort
In-Place Insertion Sort
Insertion Sort Runtime

Quicksort

Quicksort Backstory, Partitioning
Quicksort

78

79 of 104

Sorting So Far

Core ideas:

Selection sort: Find the smallest item and put it at the front.

Heapsort variant: Use MaxPQ to find max element and put at the back.

Merge sort: Merge two sorted halves into one sorted whole.
Insertion sort: Figure out where to insert the current item.

Quicksort:

Core idea: Partitioning.
Invented by Sir Tony Hoare in 1960, at the time a novice programmer.

79

80 of 104

Context for Quicksort’s Invention (Source)

1960: Tony Hoare was working on a crude automated translation program for Russian and English. �

Binary search for each word.

Find “the” in log D time.
Find “cat” in log D time...

Total time: N log D

80

...	...
beautiful	красивая
...	...
cat	кошка
...	...

“The cat wore a beautiful hat.”

Dictionary of D english words

N words

“Кошка носил красивая шапка.”

How would you do this?

81 of 104

Context for Quicksort’s Invention (Source)

Limitation at the time:

Dictionary stored on long piece of tape, sentence is an array in RAM.

Binary search of tape is not log time (requires physical movement!).

Better: Sort the sentence and scan dictionary tape once. Takes N log N + D time.

But Tony had to figure out how to sort an array (without Google!)...�

1960: Tony Hoare was working on a crude automated translation program for Russian and English.

Algorithm: N binary searches of D length dictionary.

Total runtime: N log D
ASSUMES log time binary search!

81

...	...
beautiful	красивая
...	...
cat	кошка
...	...

82 of 104

Partitioning

Main idea: I have a list of small and large items. To sort this:

Separate the small items and large items into two separate piles
Sort the small items
Sort the large items
Put the sorted lists together

How to decide what's big and what's small?

Pick an item from the list (we'll call this the pivot). Smaller items are small, and bigger items are big

We'll call this a partition; we separate the big items and the small items, and put remaining items in the middle.

82

83 of 104

Partitioning

A partition of an array, given a pivot x, is a rearrangement of the items so that:

All entries to the left of x are <= x.
All entries to the right of x are >= x.
x moves between the smaller and larger items

83

3

1

2

4

6

8

7

3

4

1

2

6

7

8

Example of a valid output

Another example of a valid output

6

8

3

1

2

7

4

Input

9

84 of 104

Core Idea of Tony’s Sort: Partitioning http://yellkey.com/TODO

A partition of an array, given a pivot x, is a rearrangement of the items so that:

All entries to the left of x are <= x.
All entries to the right of x are >= x.

Which partitions are valid?

84

5

550

10

4

10

9

330

4

5

9

10

330

550

5

9

10

4

10

550

330

5

4

9

10

550

330

5

9

10

4

10

550

330

A.

C.

B.

D.

j

85 of 104

The Core Idea of Tony’s Sort: Partitioning

A partition of an array, given a pivot x, is a rearrangement of the items so that:

All entries to the left of x are <= x.
All entries to the right of x are >= x.

Which partitions are valid?

85

5

550

10

4

10

9

330

i

4

5

9

10

330

550

5

9

10

4

10

550

330

5

4

9

10

550

330

5

9

10

4

10

550

330

A.

C.

B.

D.

j

Called the ‘pivot’.

86 of 104

Job Interview Style Question (Partitioning)

Given an array of colors where the 0th element is white (and maybe a few more), and the remaining elements are red (less) or blue (greater), rearrange the array so that all red squares are to the left of the white square, the white squares end up together, and all blue squares are to the right. Your algorithm must complete in Θ(N) time (no space restriction).

Relative order of red and blues does NOT need to stay the same.

86

3

1

2

4

6

8

7

3

4

1

2

6

7

8

Example of a valid output

Another example of a valid output

6

8

3

1

2

7

4

Input

6

87 of 104

Quicksort

Lecture 33, CS61B, Spring 2026

Insertion Sort

Naive Insertion Sort
In-Place Insertion Sort
Insertion Sort Runtime

Miscellaneous Sorts

Quicksort

Quicksort Backstory,�Partitioning
Quicksort

87

88 of 104

Quick Sort: Intuition

88

1

2

3

4

5

6

7

8

0

32

15

2

17

19

26

41

17

Input:

unsorted

32

Pick one item (“pivot”), get it in the correct spot

89 of 104

Quick Sort: Intuition

89

1

2

3

4

5

6

7

8

0

32

15

2

17

19

26

41

17

Input:

unsorted

32

Pick one item (“pivot”), get it in the correct spot

32

90 of 104

Quick Sort: Intuition

90

1

2

3

4

5

6

7

8

0

32

15

2

17

19

26

41

17

Input:

unsorted

32

Pick one item (“pivot”), get it in the correct spot

32

Get everything else on the correct side

32

91 of 104

Quick Sort: Intuition

91

1

2

3

4

5

6

7

8

0

32

15

2

17

19

26

41

17

Input:

unsorted

32

Pick one item (“pivot”), get it in the correct spot

32

Get everything else on the correct side

2

17

19

26

17

32

15

92 of 104

Quick Sort: Intuition

92

1

2

3

4

5

6

7

8

0

32

15

2

17

19

26

41

17

Input:

unsorted

32

Pick one item (“pivot”), get it in the correct spot

32

Get everything else on the correct side

2

17

19

26

17

32

41

15

<= 32

>= 32

93 of 104

Quick Sort: Intuition

93

1

2

3

4

5

6

7

8

0

32

15

2

17

19

26

41

17

Input:

unsorted

32

Pick one item (“pivot”), get it in the correct spot

32

Get everything else on the correct side

2

17

19

26

17

32

41

15

Do this to each item => sorted array

<= 32

>= 32

Each time have to look through fewer items => quick

94 of 104

Core Idea of Tony’s Sort: Partitioning http://yellkey.com/TODO

A partition of an array, given a pivot x, is a rearrangement of the items so that:

All entries to the left of x are <= x.
All entries to the right of x are >= x.

Which partitions are valid?

94

5

550

10

4

10

9

330

4

5

9

10

330

550

5

9

10

4

10

550

330

5

4

9

10

550

330

5

9

10

4

10

550

330

A.

C.

B.

D.

j

95 of 104

The Core Idea of Tony’s Sort: Partitioning

A partition of an array, given a pivot x, is a rearrangement of the items so that:

All entries to the left of x are <= x.
All entries to the right of x are >= x.

Which partitions are valid?

95

5

550

10

4

10

9

330

i

4

5

9

10

330

550

5

9

10

4

10

550

330

5

4

9

10

550

330

5

9

10

4

10

550

330

A.

C.

B.

D.

j

Called the ‘pivot’.

96 of 104

Partition Sort, a.k.a. Quicksort

Observations:

5 is “in its place.” Exactly where it’d be if the array were sorted.
Can sort two halves separately, e.g. through recursive use of partitioning.

96

5

3

2

1

8

4

6

7

3

2

1

4

7

8

6

5

3

2

1

4

5

7

8

6

5

2

1

3

4

5

6

7

8

5

Q: How would we use this operation for sorting?

97 of 104

Quick Sort

Quick sorting N items:

Partition on leftmost item.
Quicksort left half.
Quicksort right half.

97

32

15

2

17

19

26

41

17

Input:

unsorted

98 of 104

Quick Sort

Quick sorting N items:

Partition on leftmost item (32).
Quicksort left half.
Quicksort right half.

98

32

15

2

17

19

26

41

17

Input:

partition(32)

99 of 104

Quick Sort

Quick sorting N items:

Partition on leftmost item (32).
Quicksort left half.
Quicksort right half.

99

15

2

17

19

26

17

32

41

Input:

<= 32

>= 32

in its place

partition(32)

100 of 104

Quick Sort

Quick sorting N items:

Partition on leftmost item (32) (done).
Quicksort left half.
Quicksort right half.

100

15

2

17

19

26

17

32

Input:

in its place

41

partition(32)

101 of 104

Quick Sort

Quick sorting N items:

Partition on leftmost item (32) (done).
Quicksort left half (details not shown).
Quicksort right half.

101

partition(32)

partition(15)

partition(2)

partition(17)

partition(19)

partition(17)

partition(26)

x

2

15

17

19

26

32

41

Input:

in its place

x

102 of 104

Quick Sort

Quick sorting N items:

Partition on leftmost item (32) (done).
Quicksort left half (details not shown).
Quicksort right half (details not shown).

102

partition(32)

partition(15)

partition(2)

partition(17)

partition(19)

partition(17)

partition(26)

x

2

15

17

19

26

32

41

Input:

in its place

If you don't fully trust the recursion, see these extra slides for a complete demo.

x

103 of 104

Partition Sort, a.k.a. Quicksort

Quick sorting N items:

Partition on leftmost item.
Quicksort left half.
Quicksort right half.

103

32

15

2

17

19

26

41

17

partition(32)

15

2

17

19

26

17

32

41

<= 32

>= 32

in its place

104 of 104

Quicksort

Quicksort was the name chosen by Tony Hoare for partition sort.

For most common situations, it is empirically the fastest sort.

Tony was lucky that the name was correct.

How fast is Quicksort? Need to count number and difficulty of partition operations.

Theoretical analysis:

Partitioning costs Θ(K) time, where Θ(K) is the number of elements being partitioned (as we saw in our earlier “interview question”).
The interesting twist: Overall runtime will depend crucially on where pivot ends up.

104