Radix sort in Java with Example

Hello guys, in one of the interview I was asked to name any O(n) sorting algorithm. I was shocked because I only knew about QuickSort and Mergesort whose best time is O(NLogN), so I couldn't answer that question. After the interview, the first thing I did was to Google about O(n) sorting algorithm and I was surprised to find that there are many algorithms like Radix Sort and Counting Sort and Bucket Sort which can provide O(n) performance. So, I learn them and wrote articles about them like in previous article I explained about Counting Sort algorithm and in this article, I will explain Radis sort like what it is and how it works. In Radix sort, we are sorting by comparing individual digits from the last one to the first one. In essence, radix sort is like this: sort elements by the last digit. 

Then sort elements by second to the last digit up till we reach the first digit and after that, all elements are in sorted order. The sorting can be done by having buckets for each number and putting elements into each bucket (like in this explanation) or as in implementation provided here reuse counting sort.

As you can see for this method to work you need to know the largest number of digits that elements in your data set might contain (or you will need to determine that dynamically which costs time too). The complexity of the algorithm is O(kn) where k is a number of digits and n is a number of elements. If k is very big this sort might be not as efficient as even comparison sorts.

We can sort the array in O(N) using radix sort, by using a list of lists of size 10, first position denotes the buckets for 0, 10th pos for 9.

We need passes equal to the double of digits in N, as the number of digits in N^2 can be maximum double of the digits in N. To get a digit we can first divide the number with 10^i and then get the remainder after dividing by 10, where i = 0 to 2*Number of digits in N. You can understand this better by this radix sort java code snippet below.

Algorithms always depend on the input. We saw that general-purpose sorting algorithms like insertion sort, bubble sort, and quicksort can be very efficient in some cases and inefficient in others. Indeed, insertion and bubble sort are considered slow, with a best-case complexity of O(n2), but they are quite effective when the input is fairly sorted. 

So, when you have a sorted array and you add some “new” values to the array you can sort it quite effectively with insertion sort. On the other hand, quicksort is considered one of the best general-purpose sorting algorithms, but while it’s a great algorithm when the data is randomized, it’s practically as slow as bubble sort when the input is almost or fully sorted.

Now we see that the effectiveness of algorithms depends greatly on the input. For input that is almost sorted, insertion sort may be preferred instead of quicksort, which is generally a faster algorithm.

Because the input is so important for an algorithm's efficiency, we may ask if there are any sorting algorithms that are faster than O(n.log(n)), which is the average-case complexity for merge sort and quicksort. And the answer is yes there are faster, linear complexity algorithms, that can sort data faster than quicksort, merge sort, and heapsort. But there are some constraints!

Everything sounds great but we can’t sort any particular data with linear complexity, so the question is what rules must the input follow in order to be sorted in linear time?

Such an algorithm that is capable of sorting data in linear O(n) time is radix sort and the domain of the input is restricted – it must consist only of integers.

How Radix sort Algorithm works

Radix sort, like counting sort and bucket sort, is an integer-based algorithm (i.e. the values of the input array are assumed to be integers). Hence radix sort is among the fastest sorting algorithms around, in theory. 

The particular distinction for radix sort is that it creates a bucket for each cipher (i.e. digit); as such, similar to bucket sort, each bucket in radix sort must be a growable list that may admit different keys.

For decimal values, the number of buckets is 10, as the decimal system has 10 numerals/cyphers (i.e. 0,1,2,3,4,5,6,7,8,9). Then the keys are continuously sorted by significant digits.

Here is a nice diagram which explains how Radix sort works and you can calculate time complexity of Radix sort

Radix Sort Example in Java

Here is our sample Java program to implement the Radix sort algorithm.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Java Program to sort a list of integers using Radix Sort algorithm. 
 * It is one of the sophisticated sorting algorithm which provides
 * linear time complexity.
 * Radix sort take advantage of favorable condition to 
 * sort a list of integers in O(n) time.
 *
 * @author WINDOWS 8
 */
public class RadixSorting {

    public static void main(String args[]) {

        // sorting integer array using Counting Sort
        int[] random = {14, 18, 13, 12, 19, 13, 111};
        System.out.println("Unsorted random integer array : "
                + Arrays.toString(random));

        radixsort(random);
        System.out.println("Sorted integer array : "
                + Arrays.toString(random));

        // one more example
        int[] large = {32, 144, 312, 22, 141, 1, 34, 33};
        System.out.println("Unsorted array of integers : "
                + Arrays.toString(large));

        radixsort(large);
        System.out.println("Sorted integer array : " 
              + Arrays.toString(large));
    }

    /**
     * This method implements Radix sort algorithm to sort an integer array in
     * linear time.
     *
     * @param array
     */
    public static void radixsort(int[] array) {
        final int RADIX = 10;

        // declare and initialize bucket[]
        List[] bucket = new ArrayList[RADIX];
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = new ArrayList();
        }

        // radix sort algorithm
        boolean maxLength = false;
        int tmp = -1, placement = 1;
        while (!maxLength) {
            maxLength = true;

            // split input between lists
            for (Integer i : array) {
                tmp = i / placement;
                bucket[tmp % RADIX].add(i);
                if (maxLength && tmp > 0) {
                    maxLength = false;
                }
            }

            // empty lists into input array
            int a = 0;
            for (int b = 0; b < RADIX; b++) {
                for (Integer i : bucket[b]) {
                    array[a++] = i;
                }
                bucket[b].clear();
            }

            // move to next digit
            placement *= RADIX;
        }
    }

}

Output:
Unsorted random integer array : [14, 18, 13, 12, 19, 13, 111]
Sorted integer array : [12, 13, 13, 14, 18, 19, 111]
Unsorted array of integers : [32, 144, 312, 22, 141, 1, 34, 33]
Sorted integer array : [1, 22, 32, 33, 34, 141, 144, 312]

Pros and Cons of Radix sort

Here are the main advantages and disadvantages of Radix sort algorithm:

1. It’s fast
Radix sort is very fast compared to other sorting algorithms as we saw on the diagram above. This algorithm is very useful in practice because in practice we often sort sets of integers.

2. It’s easy to understand and implement
Even a beginner can understand and implement the radix sort, which is great. You need no more than a few loops to implement it.

here are some cons and limitations of the Radix sort algorithm :

1. Works only with integers
If you’re not sure about the input, you're better off not using the radix sort. We may think that our input consists only of integers and we can go for radix sort, but what if in the future someone passes floats or strings to our routine.

2. Requires additional space
Radix sort needs additional space – at least as much as the input.

Time Complexity of Radix Sort:

Here is the best, average, and worst-case time complexity of Radix Sort algorithms:

•   Best Case O(k*n); 
•   Average Case O(k*n); 
•   Worst Case O(k*n),

where k is the length of the longest number and n is the size of the input array.

If k is greater than log(n) then an n*log(n) algorithm would be a better fit. In reality, we can always change the radix to make k less than log(n).


That's all about Radix sort, one of the popular O(n) or liner time sorting algorithm. As I said, Radix sort is restricted by the input’s domain, but I must say that in practice there are tons of cases where only integers are sorted. This is when we get some data from the DB based on primary keys – typically primary in database tables are integers as well. So practically there are lots of cases of sorting integers, so radix sort may be one very, very useful algorithm and it is so cool that it is also easy to implement.

Other Data Structure and Algorithms articles you may like:

• How to impalement Insertion sort algorithm in Java (algorithm)
• How to sort an array in place using the QuickSort algorithm? [solution]
• Write a program to find the top two numbers from an integer array? [solution]
• How to check if an array contains a number in Java? [solution]
• How to find the largest and smallest number from a given array in Java? [solution]
• 7 Best courses to learn Data Structure and Algorithms (courses)
• Write a program to find the missing number in an integer array of 1 to 100? [solution]
• How do you remove duplicates from an array in place? [solution]
• How do you reverse an array in place in Java? [solution]
• 10 Free Data Structure and Algorithms Courses for Programmers [courses]
• How to find the maximum and minimum number in an unsorted array? [solution]
• Best Data Structure and Algorithm Books (books)
• 10 Algorithms courses to Crack Coding Interviews [courses]
• 30+ Array-based Coding Problems from Interviews (questions)
• How do you print all duplicate elements from the array in Java? [solution]
• 10 Algorithms Books Every Programmer should read [books]
• How to find all pairs on an integer array whose sum is equal to a given number? [solution]

Thanks for reading this article. If you like this example of Radix Sort in Java then please share it with your friends and colleagues. If you have any questions or suggestions then please drop a comment and I'll try to find an answer for you.

P. S. - If you want to learn Data Structure and Algorithms better and looking for free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.