The O(n) Sorting Algorithm of Your Dreams

Explore the genius behind LSD Radix Sort

Image sourced from Pexels

Sorting algorithms are by no means time efficient. As software engineers, we begin by learning basic sorts, like Bubble Sort, Insertion Sort, and Selection Sort. Later on, we pick up more advanced sorts, like Heapsort, Quicksort, and Mergesort. Still, most of those algorithms have a worst-case time complexity, or Big-O, of O(n²), with the other few being O(nlogn)— O(n) is nowhere to be seen.

Infographic from Big-O Cheat Sheet

Introducing LSD Radix Sort

For a sorting algorithm to have a time complexity of O(n), there surely needs to be a spark of genius behind it all. Unlike other sorting algorithms, LSD Radix Sort is non-comparative and only utilizes hashing (O(1) amortized) and simple traversals (O(n)); put these two ingredients together, and you have a worst-case O(n) sorting algorithm!

In a nutshell, Least Significant Digit (LSD) Radix Sort involves repeatedly sorting the digits that occur in each element. Assuming we are sorting a lexicographical (numerical) type, this means we order by the ones place, then the tens place, then the hundreds, thousands, etc. while always maintaining the order previously established.

Algorithm Breakdown

Enjoy this line-by-line walkthrough in Python, or if you’re a C++ developer, pseudocode.

First, we need to find how many iterations are necessary for sort the list. This is easily accomplished by traversing the list and finding the maximum number of digits that make up any one element.

numIterations = 0
for element in list:
    numIterations = max(numIterations, int(math.log10(element))+1)

Then comes the core of the algorithm.

Iterating numIterations times, we need to get the current number’s place from which to sort.

for i in range(0, numIterations):
    place = 10 ** i

Every iteration, we need to populate a separate chaining map. The keys of this map are all positive and negative digits, -9 through 9, which are commonly referred to as buckets The corresponding values are all initialized as empty lists.

map = {}
for i in range(-9, 10):
    map[i] = []
# { -9: [], -8: [], -7: [], ... , 7: [], 8: [], 9: [] }

Let’s find the digit at the current number’s place for each element and append that element to the corresponding bucket. If the element does not contain enough significant digits, the 0 bucket is used.

for element of list:
    bucket = (element // place) % 10
    map[bucket].append(element)

Next, let’s perform an in-order traversal of the map, effectively dumping the map into a list sorted according to the current number’s place. Note that the previous order is preserved because elements populate the separate chained lists in the order they are encountered.

currentIndex = 0
for elements in map.values():
    for element in elements:
        list[currentIndex] = element
        currentIndex += 1

That’s it! The algorithm will repeat this process until the list is sorted.

Tracing Example

To further understand how LSD Radix Sort manipulates an unsorted list, let’s walk through an example.

Imagine we start with a list [45, 986, 24, 3000, 7, 43, -1000, 949]. Immediately, we know that the algorithm will require 4 iterations, since 3000 and -1000 contains 4 digits.

During the first iteration (order by one’s place), the elements form the following map

{
  0: [3000, -1000],
  3: [43],
  4: [24],
  5: [45],
  6: [986],
  7: [7],
  9: [949]
}

which when traversed, results in the list [3000, -1000, 43, 24, 45, 986, 7, 949].

Let’s rinse and repeat for the remaining three iterations.

Iteration 2 (tens place):

{
  0: [3000, -1000, 7],
  2: [24],
  4: [43, 45, 949],
  8: [986]
}
[3000, -1000, 7, 24, 43, 45, 949, 986]

Iteration 3 (hundreds place):

{
  0: [3000, -1000, 7, 24, 43, 45],
  9: [949, 986]
}
[-1000, 7, 24, 43, 45, 949, 986]

Iteration 4 (thousands place):

{
  -1: [-1000],
  0: [7, 24, 43, 45 949, 986],
  3: [3000]
}
[-1000, 7, 24, 43, 45, 949, 986, 3000]

Voila! After 4 iterations, the unsorted list[45, 986, 24, 3000, 7, 43, -1000, 949] transforms into the sorted list[-1000, 7, 24, 43, 45, 949, 986, 3000].

Big-O != Efficiency

Sure, LSD Radix Sort is the most efficient sorting algorithm — on paper.

There’s a major difference between technical time complexity and real-world efficiency. Big-O, for the most part, ignores constants and focuses on the function’s growth. In practice, the constants not present in Big-O notation make a significant difference in program runtime, since the number of total operations is what really matters.

So How Efficient is LSD Radix Sort, Really?

Taking constants into account, this algorithm has a time complexity of O(mn), where n is list length, and m is the average element length (number of radices). This makes sense since the map traversal uses n operations, and this whole process must be repeated through m iterations.

When to Use LSD Radix Sort

When m is very small, LSD Radix Sort is at its prime. This is when the number of hashing iterations and traversals is minimized.

On the other hand, if m is large, then LSD Radix Sort will have a proportionately long runtime. To put this scenario into perspective, as m approaches n, Big-O approaches O(n²): exactly the inefficiency we wanted to avoid in the first place. If this is the case, it is worth considering implementing Mergesort or Heapsort, whose worst-case time complexities are O(nlogn).

Conclusion

Thanks for reading my article, I hope you’ve found it helpful. Feel free to leave feedback or questions in the comments section.