How to implement Radix Sort in Java - Algorithm Example [Solved]

The Radix sort, like counting sort and bucket sort, is an integer-based algorithm (I mean the values of the input array are assumed to be integers). Hence radix sort is among the fastest sorting algorithms around, in theory. It is also one of the few O(n) or linear time sorting algorithms along with the Bucket and Counting sort. 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.

Time Complexity of radix sort in the best case, average case, and worst case is O(k*n) where k is the length of the longest number, and n is the size of the input array.

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

Btw, if you are not familiar with time and space complexity and how to calculate or optimize it for a particular algorithm then I suggest you first go through a fundamental algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy.  This will not only help you to do well in interviews but also in your day-to-day job.

Java program to implement Radix sort algorithm

Before solving this problem or implementing a Radix Sort Algorithm, let's first get the problem statement right:

Problem Statement:

Given a disordered list of integers, rearrange them in the natural order.

Sample Input: {18,5,100,3,1,19,6,0,7,4,2}
Sample Output: {0,1,2,3,4,5,6,7,18,19,100}

Solution

Here is a sample program to implement the Radix sort algorithm in Java

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

/*
 * Java Program sort an integer array using radix sort algorithm.
 * input: [180, 50, 10, 30, 10, 29, 60, 0, 17, 24, 12]
 * output: [0, 10, 10, 12, 17, 24, 29, 30, 50, 60, 180]
 * 
 * Time Complexity of Solution:
 *   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.
 *
 *   Note: 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).
 * 
 */

public class Main {

  public static void main(String[] args) {

    System.out.println("Radix sort in Java");
    int[] input = { 181, 51, 11, 33, 11, 39, 60, 2, 27, 24, 12 };

    System.out.println("An Integer array before sorting");
    System.out.println(Arrays.toString(input));

    // sorting array using radix Sort Algorithm
    radixSort(input);

    System.out.println("Sorting an int array using radix sort algorithm");
    System.out.println(Arrays.toString(input));

  }

  /**
   * Java method to sort a given array using radix sort algorithm
   * 
   * @param input
   */
  public static void radixSort(int[] input) {
    final int RADIX = 10;
    
    // declare and initialize bucket[]
    List<Integer>[] bucket = new ArrayList[RADIX];
    
    for (int i = 0; i < bucket.length; i++) {
      bucket[i] = new ArrayList<Integer>();
    }

    // sort
    boolean maxLength = false;
    int tmp = -1, placement = 1;
    while (!maxLength) {
      maxLength = true;
      
      // split input between lists
      for (Integer i : input) {
        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]) {
          input[a++] = i;
        }
        bucket[b].clear();
      }
      
      // move to next digit
      placement *= RADIX;
    }
  }
}

Output
Radix sort in Java
An Integer array before sorting
[181, 51, 11, 33, 11, 39, 60, 2, 27, 24, 12]
Sorting an int array using radix sort algorithm
[2, 11, 11, 12, 24, 27, 33, 39, 51, 60, 181]

Here is another example of sorting a list of an integer using Radix sort, just in case If you haven't got the concept of how Radix sort works:

Problem Statement:

Sort the list of numbers 10, 52, 5, 209, 19,  and 44 using the Radix sort algorithm:

Solution:

That's all about how to sort an integer array using radix sort in Java. Along with Counting Sort and Bucket sort, it is also an O(n) sorting algorithm. These algorithms are not general-purpose and you cannot use them to sort any object like String, Employee, etc. They are best suited for a small range of known integer values but they provide awesome performance.

More Data Structure  and Algorithms Problems for Practice
If you are interested in solving more Data Structure and algorithm problems then here is the list of some of the frequently asked questions.

• How to convert a numeric string to an int? (solution)
• 100+ Data Structure and Algorithms Problems (solved)
• 10 Books to learn Data Structure and Algorithms (books)
• How to check if two given Strings are Anagram in Java? (solution)
• 10 Data Structure and Algorithms course to crack coding interview (courses)
• 101 Coding Problems and a few tips for Tech interviews (tips)
• When to use ArrayList vs LinkedList in Java? (answer)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• Top 5 Books to Learn Data Structure and Algorithms (books)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Top 5 Books for Programming and Coding Interviews (books)
• 10 Free Courses to learn Data Structure and Algorithms (courses)
• How to convert a linked list to an array in Java? (example)
• My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
• What is the difference between LinkedList and ArrayList in Java? (answer)
• 21 String coding Problems from Technical Interviews (questions)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
• How to reverse words in a sentence without using a library method? (solution)
• How to reverse a String in place in Java? (solution)
• How to return the highest occurred character in a String? (solution)
• 50+ Data Structure and Algorithms Interview Questions (questions)

Thanks for reading this article so far. If you like this Radix sort example in Java then please share it with your friends and colleagues. If you have any questions or feedback then please drop a note. Btw, what is your favorite O(1) algorithm Radix sort, Counting Sort or Bucket Sort?

P. S. - If you are looking for some Free Data Structure and Algorithms courses to improve your understanding of essential data Structure and algorithms, then you should also check these free Data Structures in Java for the Beginners course on Udemy. It's a free and great course to refresh data structure fundamentals for Java Programmers.