As far as sorts go, Radix Sort's the crotchety old man sitting on his front porch reminiscing about the good old days—the good old days being the 1890s. Digital computers are younger than radix sort (source). Yeah, it's that old.

Unlike most sorts, Radix Sort doesn't compare to sort. Instead, it groups the values of integers to get closer to a sorted list. Let's look at an example.

Except let's shake things up a bit and look at the numbers in columns this time.

If this were Merge Sort or Bubble Sort, we'd start making comparisons between numbers. Radix Sort couldn't care less about how these numbers compare; it just wants to stack them. This time we're going to start with the smallest decimal place and move larger, but we could do it the opposite way if we wanted to.

If we put all the numbers into buckets based on the ones place, we'll get something like this:

0: 920
3: 593
4: 904
6: 646, 556
8: 148

Now that we've sorted everything by the ones place, we're going to go through and sort by the tens place. If two numbers tie, we need to make sure that the number that came before in the last round stays ahead of the one that came behind it.

0: 904
2: 920
4: 646, 148
5: 556
9: 593

Because we kept the order from last time, everything's is ordered from the tens place down. If we do the same thing for the hundreds place:

1: 148
5: 556, 593
6: 646
9: 904, 920

We've completely ordered the list.

Moving left- right, up-down, the ordered list is:

Aw yeah.

After going through the list of n elements once for each integer, this sort's virtually O(n), which is significantly better than O(nlogn) and O(n²).

If we start working with numbers with thousands of digits, though, we'd have to worry about just how many times we'd need to go through the list. If we call the number of digits in each number k, the runtime's actually O(kn). When k gets big enough, a different sort will probably run faster.

Even so. Not bad for an old fogey algorithm.