**Ursinus CS 271: Data Structures And Algorithms, Fall 2023**

## Week 8: Radix Sort

### Chris Tralie

## Overview / Logistics

We saw in class (click here for a video) that the lower bound for any possible sort that's based on comparisons is **Ω(N log(N))**. So if we have any hope of beating this, we have to think of a completely different strategy. We'll start with a simple example first known as "counting sort"

## Counting Sort

What we can do is have a bunch of "bins" or "buckets," ordered in sequence in an array, where there's a bin for each possible value in our list. We can then loop through the bins from left to right and extract the elements in order. The code below shows this

### Question

What is the time and space complexity of the above algorithm?## Radix Sort

Depending on the maximum element, counting sort can be pretty inefficient. But there's a way to use it as a subroutine in a more efficient sort. If we're careful on how we implement counting sort, it can be done so that it's stable. What we can do, then, is apply counting sort **one digit at a time**, from the right most digit left. This is known as **Least Significant Digit Radix Sort**. The table below shows this.

Original Order | 684 | 559 | 629 | 192 | 835 | 763 | 707 | 359 | 9 | 723 | 277 | 754 | 804 | 599 | 70 | 472 | 600 | 396 | 314 | 705 |

1s Place | 70 | 600 | 192 | 472 | 763 | 723 | 684 | 754 | 804 | 314 | 835 | 705 | 396 | 707 | 277 | 559 | 629 | 359 | 9 | 599 |

10s Place | 600 | 804 | 705 | 707 | 9 | 314 | 723 | 629 | 835 | 754 | 559 | 359 | 763 | 70 | 472 | 277 | 684 | 192 | 396 | 599 |

100s Place | 9 | 70 | 192 | 277 | 314 | 359 | 396 | 472 | 559 | 599 | 600 | 629 | 684 | 705 | 707 | 723 | 754 | 763 | 804 | 835 |