Radix Sorts

1

Lecture 36 (Sorting 5)

CS61B, Spring 2025 @ UC Berkeley

Slides credit: Josh Hug

Sorting Stability

Lecture 36, CS61B, Spring 2025

Sorting Stability

Warmup: Digit-by-digit Sorting

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

Sorting Summary (so far)

Listed by mechanism:

• Selection sort: Find the smallest item and put it at the front.
• Insertion sort: Figure out where to insert the current item.
• Merge sort: Merge two sorted halves into one sorted whole.
• Partition (quick) sort: Partition items around a pivot.

Listed by memory and runtime:

​

Other Desirable Sorting Properties: Stability

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

sort(studentRecords, BY_NAME);

sort(studentRecords, BY_SECTION);

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

Other Desirable Sorting Properties: Stability

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

sort(studentRecords, BY_NAME);

sort(studentRecords, BY_SECTION);

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

Sorting Stability

Is insertion sort stable?

​

​

​

​

​

​

Is Quicksort stable?

• Consider -------->

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)

6

8

3

1

2

7

4

Sorting Stability

Is insertion sort stable?

• Yes.
• Equivalent items never move past their equivalent brethren.

​

Is Quicksort stable?

• Depends on your partitioning strategy.

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)

6

7

3

1

2

8

3

2

3

3

1

6

8

7

3

1

2

3

6

7

8

Hoare partitioning.

Three array partitioning.

Stability

You can create a stable Quicksort (i.e. the version from the previous lecture). However, unstable partitioning schemes (like Hoare partitioning) tend to be faster. All reasonable partitioning schemes yield Θ(N log N) expected runtime, but with different constants.

This is due to the cost of tracking recursive calls by the computer, and is also an “expected” amount. The difference between log N and constant memory is trivial.

Arrays.sort

In Java, Arrays.sort(someArray) uses:

• Mergesort (specifically the TimSort variant) if someArray consists of Objects.
• Quicksort if someArray consists of primitives.

​

Why? See A level problems.

​

​

Arrays.sort

In Java, Arrays.sort(someArray) uses:

• Mergesort (specifically the TimSort variant) if someArray consists of Objects.
• Quicksort if someArray consists of primitives.

​

Why?

• Quicksort isn’t stable, but there’s only one way to order them. Wouldn’t have multiple types of orders.
• Could sort by other things, say sum of the digits.
• Order by number of digits.
• My usual answer: 5 is just 5. There’s no different possible 5s.

​

​

Arrays.sort

In Java, Arrays.sort(someArray) uses:

• Mergesort (specifically the TimSort variant) if someArray consists of Objects.
• Quicksort if someArray consists of primitives.

​

Why?

• When you are using a primitive value, they are the ‘same’. A 4 is a 4. Unstable sort has no observable effect.
• There’s really only one natural order for numbers, so why not just assume that’s the case and sort them that way.
• By contrast, objects can have many properties, e.g. section and name, so equivalent items CAN be differentiated.
• If you know there’s only one way, can you force Java to use Quicksort?

​

​

Optimizing Sorts

Additional tricks we can play:

• Switch to insertion sort:
• When a subproblem reaches size 15 or lower, use insertion sort.
• Make sort adaptive: Exploit existing order in array (Insertion Sort, SmoothSort, TimSort (the sort in Python and Java)).
• Exploit restrictions on set of keys. If number of keys is some constant, e.g. [3, 4, 1, 2, 4, 3, …, 2, 2, 2, 1, 4, 3, 2, 3], can sort faster (see 3-way quicksort -- if you’re curious, see: http://goo.gl/3sYnv3).
• For Quicksort: Make the algorithm introspective, switching to a different sorting method if recursion goes too deep. Only a problem for deterministic flavors of Quicksort.

Today’s Two New Ideas

Today we’ll cover two new ideas:

• Digit-by-Digit Sorting
• A procedure that uses a sort (e.g. Merge Sort, Quicksort, Counting Sort).
• Using the word “sort” is arguably a misnomer.
• Digit-by-digit sorting is a process that uses another sort as a subroutine.
• Counting Sort
• A new type of sort that competes with Merge Sort, Quicksort, Heap Sort, Insertion Sort, Selection Sort, etc.
• Unlike these other sorts, Counting Sort does not use compareTo.

Warmup: Digit-by-digit Sorting

Lecture 36, CS61B, Spring 2025

Sorting Stability

Warmup: Digit-by-digit Sorting

Counting Sort

• Procedure
• Runtime

Radix Sorts

• LSD Radix Sort
• MSD Radix Sort

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.

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.

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.

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.

I put 53 and 23 in this order. 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.

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

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.

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.

Digit-by-digit Sorting

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

Digit-by-digit Sorting

Example of a digit-by-digit sort:

• Use a stable sort on each digit, moving from least to most significant.
• Result is guaranteed to correct!

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.

Last digit is 3

Mid digit is 3

Top digit is 3

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

The Counting Sort Algorithm

Lecture 36, CS61B, Spring 2025

Sorting Stability

Warmup: Digit-by-digit Sorting

Counting Sort

• The Counting Sort Algorithm
• Runtime

Radix Sorts:

• LSD Radix Sort
• MSD Radix Sort

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?

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)

​

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

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

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

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

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

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.

Counting Sort

Alphabet case: Keys belong to a finite ordered alphabet.

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

​

​

​

​

​

​

​

​

​

​

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

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 ♥?

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.

​

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

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

Counts

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points

0

1

2

3

4

5

6

7

8

9

10

11

Sorted

Counting Sort

Example:

• Alphabet: {♣, ♠, ♥, ♦}

0

1

2

3

0

1

2

3

Counts

Starting Points