1

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

Radix Sorts

2

Lecture 36 (Sorting 5)

CS61B, Spring 2026 @ UC Berkeley

Josh Hug and Manuel Sabin

Review session Friday!

4:30-7pm in Dwinelle

Sorting Stability

Lecture 36, CS61B, Spring 2026

Sorting Stability (Section Review)

Sorting Digit-by-Digit

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

3

Section Worksheet

This week, I introduced a new topic on the discussion worksheet: Stability.

​

Let’s review this idea since it’s important for today’s lecture.

• Note: Stability will be in scope for the final, e.g.
• “Is insertion sort stable?”
• “If you sort this array using an unstable sort, which of the following outputs are possible.”
• “Why does Java use Quicksort for ints and Merge Sort for objects?”
• The discussion worksheet provides practice with the idea of stability.

4

Section Topic Review: Stability

A sort is said to be stable if order of equivalent items is preserved.

5

sort(studentRecords, BY_NAME);

sort(studentRecords, BY_SECTION);

Equivalent items don’t ‘cross over’ when being stably sorted.

Section Topic Review: Stability

​

A sort is said to be stable if order of equivalent items is preserved.

6

sort(studentRecords, BY_NAME);

sort(studentRecords, BY_SECTION);

Sorting instability can be really annoying! Wanted students listed alphabetically by section.

Sorting Digit-by-Digit

Lecture 36, CS61B, Spring 2026

Sorting Stability (Section Review)

Sorting Digit-by-Digit

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

7

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

8

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

9

What are the 4 integers at the end of the array?

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

10

Digit-by-digit Sorting: https://www.yellkey.com/still

​

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

11

I put 53 and 23 in the order shown. Would they always be in this order?

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Suppose we first sort by only the rightmost digit.

12

I put 53 and 23 in this order. Would they always be in this order?

• Not necessarily! Depends on if the sort I used is stable.
• Stable sort yields 53 then 23.
• Example: If I used Quicksort with shuffle, could have been 23 then 53.

Digit-by-digit Sorting (NO POLL)

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Now suppose we sort by the left digit using a stable sort.

13

In what order will 31,

32, 34, and 34 appear?

Digit-by-digit Sorting

As a warmup to the later part of today’s lecture. Suppose we have a list of integers we want to sort.

• Now suppose we sort by the left digit using a stable sort.

14

Digit-by-digit Sorting

This procedure does not work if the sort subroutine is unstable.

15

Digit-by-digit Sorting

This is sometimes called “LSD sort” or “Least Significant Digit” sort.

• Select a stable sorting algorithm e.g. insertion sort, merge sort, etc.
• Use that stable sort on each digit, moving from least to most significant.
• Result of LSD sort is guaranteed to correct (iff the sort is stable)!

16

Last digit is 3

Mid digit is 3

Top digit is 3

Digit-by-digit Sorting

Two quick notes:

• No obvious reason why this procedure is useful (can just sort by entire integer)
• Other digit-by-digit sort procedures work.

17

Last digit is 3

Mid digit is 3

Top digit is 3

We’ll come back to digit-by-digit sorting later!

Counting Sort: Procedure

Lecture 36, CS61B, Spring 2026

Sorting Stability (Section Review)

Sorting Digit-by-Digit

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

18

Comparison Based Sorting

The key idea from our previous sorting lecture: Sorting requires Ω(N log N) compares in the worst case.

• Thus, the ultimate comparison based sorting algorithm has a worst case runtime of Θ(N log N).

​

From an asymptotic perspective, that means no matter how clever we are, we can never beat Merge Sort’s worst case runtime of Θ(N log N).

• ...but what if we don’t compare at all?

19

Example #1: Sleep Sort (for Sorting Integers) (not actually good)

For each integer x in array A, start a new program that:

• Sleeps for x seconds.
• Prints x.

​

All start at the same time.

​

Runtime:

• N + max(A)

​

20

Example #2: Counting Sort: Exploiting Space Instead of Time

21

Assuming keys are unique integers 0 to 11.

​

Idea:

• Create a new array.
• Copy item with key i into ith entry of new array.

Example #2: Counting Sort: Exploiting Space Instead of Time

22

Example #2: Counting Sort: Exploiting Space Instead of Time

23

Example #2: Counting Sort: Exploiting Space Instead of Time

24

Example #2: Counting Sort: Exploiting Space Instead of Time

25

Generalizing Counting Sort

We just sorted N items in Θ(N) worst case time.

• Avoiding yes/no questions lets us dodge our lower bound based on puppy, cat, dog!

​

Simplest case:

• Keys are unique integers from 0 to N-1.

​

More complex cases:

• Non-unique keys.
• Non-consecutive keys.
• Non-numerical keys.

26

Counting Sort: http://yellkey.com/always

Alphabet case: Keys belong to a finite ordered alphabet.

• Example: {♣️, ♠️, ♥️, ♦️} (in that order)

​

​

​

​

​

​

​

​

​

Question: What will be the index of the first ♥️?

27

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Alphabet case: Keys belong to a finite ordered alphabet.

• Example: {♣️, ♠️, ♥️, ♦️} (in that order)

​

​

​

​

​

​

​

​

​

Question: What will be the index of the first ♥️?

28

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Implementing Counting Sort with Counting Arrays

Counting sort:

• Count number of occurrences of each item.
• Iterate through list, using count array to decide where to put everything.
• Slide Demo

​

Bottom line, we can use counting sort to sort N objects in Θ(N) time.

29

Counting Sort: Runtime

Lecture 36, CS61B, Spring 2026

Sorting Stability (Section Review)

Sorting Digit-by-Digit

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

30

Counting Sort vs. Quicksort: http://yellkey.com/decade

For sorting an array of the 100 largest cities by population, which sort do you think has a better expected worst case runtime in seconds?

1. Counting Sort (as described in our demo)
2. Quicksort

​

​

First question to ask yourself: What is the alphabet for counting sort here?

​

​

​

31

Example input:

Counting Sort vs. Quicksort: http://yellkey.com/sing

For sorting an array of the 100 largest cities by population, which sort do you think has a better expected worst case runtime in seconds?

• Counting Sort (as described in our demo)
1. The alphabet for counting sort is {1, 2, 3, …, 36953600}
• Quicksort

​

Counting sort requires building an array of size 36,953,600 (population of Tokyo).

​

​

32

Counts

...

Counting Sort Runtime Analysis: yellkey.com/study

What is the runtime for counting sort on N keys with alphabet of size R?

• Treat R as a variable, not a constant.

​

This is a tough question!

​

The slide demo might be helpful.

​

​

​

​

​

​

33

Counting Sort Runtime Analysis

Total runtime on N keys with alphabet of size R: Θ(N+R)

• Creating and filling our count-related arrays: Θ(R)
• Example: R = 4 for four card suits.
• Counting each item and copying into new array: Θ(N)

​

​

​

​

​

Memory usage: Θ(N+R)

​

Bottom line: If N is ≥ R, then we expect reasonable performance.

34

See hidden slide after this for a more verbose explanation.

Counting Sort Runtime Analysis

Total runtime on N keys with alphabet of size R: Θ(N+R)

• Create an array of size R to store counts: Θ(R)
• Counting number of each item: Θ(N)
• Calculating target positions of each item: Θ(R)
• Creating an array of size N to store ordered data: Θ(N)
• Copying items from original array to ordered array: Do N times:
• Check target position: Θ(1)
• Update target position: Θ(1)
• Copying items from ordered array back to original array: Θ(N)�

​

Memory usage: Θ(N+R)

​

Bottom line: If N is ≥ R, then we expect reasonable performance.

35

Counting Sort vs. Quicksort: http://yellkey.com/garden

Give an example of a specific situation where Counting Sort will be clearly faster than Quicksort.

• Counting Sort: Θ(N+R)
• Quicksort: Θ(N log N)

​

Previous example was sorting N = 100 cities by population (R = 37,832,892).

36

Sort Summary

Counting sort is nice, but alphabetic restriction limits usefulness.

• Idea: Let’s try digit-by-digit sorting.
• The set of possible digits will be a relatively small alphabet.

N: Number of keys. R: Size of alphabet.

37

LSD Radix Sort

Lecture 36, CS61B, Spring 2026

Sorting Stability (Section Review)

Sorting Digit-by-Digit

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

38

Digit by Digit Sorting (Redux)

Counting sort is slow when the alphabet is large.

• By decomposing input into a string of characters from a finite alphabet, we can force R to be small.

39

Digit by Digit Sorting (Redux)

As we’ve seen, we can sort each digit independently from rightmost digit towards left.

• Example over the alphabet {♣️, ♠️, ♥️, ♦️}

40

LSD (Least Significant Digit) Radix Sort -- Using Counting Sort

As we’ve seen, we can sort each digit independently from rightmost digit towards left.

• Example over the alphabet {1, 2, 3, 4}

41

LSD Radix Sort

Non-comparison based sorting algorithms that proceed digit-by-digit are called “Radix Sorts”.

​

Via wikipedia: “In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers.”

​

The sort we’ve just discussed is called “LSD Radix Sort”.

• LSD: Least Significant Digit.

42

LSD Radix Sort Runtime http://yellkey.com/these

​

What is the runtime of LSD Radix sort?

• Pick appropriate letters to represent non-constant terms.
• Recall runtime for counting sort was Θ(N+R).

43

LSD Runtime

What is the runtime of LSD sort?

• Θ(WN+WR)
• N: Number of items, R: size of alphabet, W: Width of each item in # digits

44

Non-equal Key Lengths

After processing least significant digit, we have array shown below. Now what?

​

45

Non-equal Key Lengths

When keys are of different lengths, can treat empty spaces as less than all other characters.

46

Sorting Summary

W passes of counting sort: Θ(WN+WR) runtime.

• Annoying feature: Runtime depends on length of longest key.

​

​

N: Number of keys. R: Size of alphabet. W: Width of longest key.

*: Assumes constant compareTo time.

47

MSD Radix Sort

Lecture 36, CS61B, Spring 2026

Sorting Stability (Section Review)

Sorting Digit-by-Digit

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

48

MSD (Most Significant Digit) Radix Sort

Basic idea: Just like LSD, but sort from leftmost digit towards the right.

49

MSD Sort Question: http://yellkey.com/maintain

Suppose we sort by topmost digit, then middle digit, then rightmost digit. Will we arrive at the correct result? A. Yes, B. No

50

MSD Sort Question

Suppose we sort by topmost digit, then middle digit, then rightmost digit. Will we arrive at the correct result? A. Yes, B. No. How do we fix?

51

MSD Radix Sort (correct edition)

Key idea: Sort each subproblem separately.

52

Runtime of MSD

What is the Best Case of MSD sort (in terms of N, W, R)?

​

What is the Worst Case of MSD sort (in terms of N, W, R)?

​

​

Again, recall counting sort is Θ(N + R).

• And LSD radix sort was just W counting sorts, so it was WN + WR.�

​

No Poll

53

Runtime of MSD

Best Case.

• We finish in one counting sort pass, looking only at the top digit: Θ(N + R)

​

Worst Case.

• We have to look at every character, degenerating to LSD sort: Θ(WN + WR)
• In other words, we do W counting sorts.

54

Sorting Runtime Analysis

​

​

​

N: Number of keys. R: Size of alphabet. W: Width of longest key.

*: Assumes constant compareTo time.

55

Closing Plug

56

Sounds of Sorting Algorithms

Starts with selection sort: https://www.youtube.com/watch?v=kPRA0W1kECg

Insertion sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=0m9s

Quicksort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=0m38s

Mergesort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m05s

Heapsort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m28s

LSD sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=1m54s

MSD sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=2m10s

Shell’s sort: https://www.youtube.com/watch?v=kPRA0W1kECg&t=3m37s

Questions to ponder (later… after class):

• How many items are sorted in the video for selection sort?
• Why does insertion sort take longer / more compares than selection sort?
• At what time stamp does the first partition complete for Quicksort?
• Could the size of the input used by mergesort in the video be a power of 2?
• What do the colors mean for heapsort?
• How many characters are in the alphabet used for the LSD sort problem?
• How many digits are in the keys used for the LSD sort problem?

57

Citations

Creepy eye thing, title slide: http://photos3.meetupstatic.com/photos/event/a/3/f/4/highres_335141972.jpeg

​

58