Computer Sciences taught you the best time complexity to sort N elements is O(NLogN)? That’s a lie! I’ll show you how to do it in linear complexity! Brace yourself. I love algorithms and this sort of tricks helped me achieve best-in-class performance on embedded devices and for financial applications.

We’ll work with a test case in a few steps.

1. I’ll introduce my version of Counting sort that trades off time complexity for space complexity.
2. We’ll will optimize space complexity as well, using Radix Sort
3. And again, Bucket Sort.
4. We’ll put everything together.
5. Finally, we generalize how we sorted integer numbers to any item that has a defined compareTo function.

Step 1 – Counting Sort

Let’s sort the array [55, 14, 5, 7, 6, 11, 2, 60] using my optimized version of “Counting sort”.

1. Run through the array (a), in O(N), and note maximum and minimum, in our example 60 and 2.
2. Create an auxiliary array (a2) with all elements to 0 and size max-min+1, with space complexity O(max(a)). In this case, [0,0,0, … , 0] (59 zeroes).
3. Run through the original array and for each item, count the occurrences in the secondary array by increasing occurrences a2[a[i]-min]++. So the first element a2[0] will be 1, because 2, the minimum, has 1 occurrence. a2[1] will be 0 because there is no 3. a2[2] == 0 because there is no 4. a2[3] == 1 because there is 1 occurrence of 5. And so on. The array will look like [1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, … , 0, 1]
4. Then iterate through a2 in O(max(a)) and transform it into a cumulative sum [1, 1, 1, 2, 3, 4, 4, 4, …, 6, 6, 7, 7, 7, …, 8] where each element at index i is the sum of previous counts up to i. This will give us the position of each number in the sorted array.
5. Finally create a new array a3 with size N. Traverse the original array in O(N), and for each element place it in the index indicated in the cumulative count minus 1, AND decrement the count in a2. This is crucial to make it work if there are duplicate values, as they will fill in the adjacent indexes. For example place 60 in a3[a2[60-min(a)]-1] which is 8-1 = 7. Therefore a3[7] = 60.
6. a3 will be the sorted array.

Final complexity: time O(N), space O(max(a))

Now, the problem is that the original array may contain numbers too far apart, like [0,1,2,1000000,14] and so this requires an auxiliary array a2 of size 1000000. The memory allocation that completely defeats the point. Let’s proceed to step 2.

Step 2 – Radix Sort

The idea is to perform a Counting sort on an alphabet of only 10 digits (0,1,2,3,4,5,6,7,8,9) so the auxiliary array a2 has size 10. But perform it a number of times equal to the maximum numbers of digits in the largest element of a.

1. Find the number of digits of the maximum. In our sample case, 55 and 60 have 2 digits.
2. Use counting sort with an auxiliary array a2 with size 10. The array when sorted by units digit: [60, 11, 2, 14, 55, 5, 6, 7]. Explanation: Sorted by units digit (0 in 60, 1 in 11, 2 in 2, 4 in 14, 5 in 55 and 5, 6 in 6, 7 in 7).
3. Now, extract the tens digit of each number and perform Counting Sort again. When numbers have no tens digit (like 5, 6, 7), treat the tens digit as 0. The array when sorted by tens digit: [2, 5, 6, 7, 11, 14, 55, 60]. Explanation: Sorted by tens digit (0 for 2, 5, 6, 7, 1 for 11 and 14, 5 for 55, 6 for 60).
4. After these two iterations, the array is sorted: [2, 5, 6, 7, 11, 14, 55, 60]

So if the max digits are D (in our example 2), then:

Final complexity: time O(N*D), space O(D*10)

So now we have to bring time complexity down. Let’s proceed with Step 3

Step 3 – Bucket Sort

As preparatory step, I’ll introduce a new algorithm, Bucket Sort.

1. Decide a number of buckets. For example, 10 buckets.
2. In our example, min == 2 and max == 60, so, say each bucket holds (60 -2) /10 = a range of around 6 numbers. B1 represents 0 to 5. B1 represents 6 to 11, etc. You can easily scroll the original array a and map each value to a bucket with this “hashing” function. So in our silly example: B0: [2, 5], B1: [6, 7], B2: [14, 11], B5: [], B9: [55], B10: [60], Rest are empty. Let’s do 11 buckets because I don’t want to change the example.
3. Now apply Counting Sort for each bucket. After sorting each bucket, we have: B0: [2, 5], B1: [6, 7], B2: [11, 14], B5: [], B9: [55], B10: [60], Rest are empty.
4. Concatenate the buckets and obtain [2, 5, 6, 7, 11, 14, 55, 60]

Let’s consider B as the number of buckets. If there are N input elements, the worst-case space complexity can be as high as O(N+B), where N is the space for storing the input elements in the buckets, and B is the space for the buckets themselves.

Final Complexity: time O(N) + concat, space O(N+B)

The problem is B can be very large when max(a) is large and there can be empty or imbalanced buckets when data in a is not uniformely distributed over [0, max(a)].

Step 4 – Putting everything together

So now let’s put everything we learned together. Take the original array, find max and min and number of digits.

Divide in D buckets. Repartition numbers based on the number of digits. For example if min == 1 and max == 1000, B0 contains numbers from 0 to 9, B1 from 10 to 99, B2 from 100 to 999 and B4 contains 1000 to 9999. Yes, the buckets will be heavily unbalanced. This is not what we normally want with pure bucket sort.

But instead, do a radix sort of each bucket. This will be heavily optimized, because radix sort performs well when every integer has the same amount of digits.

Lastly, concatenate all sorted buckets. This is where we avoid much of the hidden complexity of the radix sort, where by adding extra zeroes when there are no digits, and putting everything together at every rearranging step, there are repeated calculations. And the concatenation is fast.

Voit-la!

Final complexity: time: O(N*D), space O(D*10+B)… but despite what it seem, this is optimized to tend to, practically O(N) and O(10*D) and if you recycle the size-10 array for all radix sorts, space complexity becomes O(10) – constant.

Step 5 – Sort non integers

This algorithm works with ints and for everything that can be hashed to int, like dates, as timestamps.

For everything else, as an intuition, you can imagine to create a hash table with an int representation. This has a space complexity of O(N) and requires a hashing function that has a compareTo similar to ints. That’s doable for strings, using a lexicographical sort convertible to ints, and for a bunch of other entities like geographical coordinates, using the geoloc hashing function that allows binary search by making lexicographical proximity behave like geographical proximity. After the entire sort algorithm, use the index to retrieve the values of the original elements from the hash table.