# Radix Sort Algorithm: What It Is, Time Complexity, Example, Advantages & Disadvantages

Radix Sort Algorithm: In this tutorial, we will learn about the radix sort, its time complexity, examples, advantaged, and disadvantages. By Prerana Jain Last updated : August 12, 2023

## Radix Sort

Radix sort is based on a linear sorting algorithm which is useful for sorting integers or strings with fixed-size keys. Radix sort uses the technique of sorting the elements digit by digit. It is an efficient sorting algorithm for integers or strings with fixed-size keys. Radix sort has also been called bucket sort and digital sort. In other words, we can say that Radix sort is a method that can be used to sort a list of a number by its base. If we want to sort the list of English words, where radix or base is 26 then 26 buckets are used to sort the words.

To sort an array of decimal number where the radix or base is 10 we need 10 buckets and can be numbered as 0,1,2,3,4,5,6,7,8,9. A number of passes required to have a sorted array depend upon the number of digits in the largest element.

## Radix Sort Algorithm

The following are the steps with an example of implementing the Radix sort:

Let **A** be a linear array of **n** elements **A[1], A[2], A[3], ..., A[n]**. Digit is the total number of digit in the largest element in array **A**.

- Input n number of elements in an array A.
- Find the total number of digits in the largest element in the array.
- Initialize i=1 and repeat the steps 4 and 5 until( i<=Digit).
- Initialize the bucket j=0 and repeat the steps 5until (j<n).
- Compare the i
^{th}position of each element of the array with bucket number and place it in the corresponding bucket. - Read the elements (S) of the bucket from 0
^{th}bucket to 9^{th}bucket and from the first position to the higher one to generate new array A. - Display the sorted array A.
- Exit.

## Radix Sort Time Complexity

Time requirement for the **radix sorting method** depends on the number of digits and the elements in the array. Suppose **A** is an array of **n** elements **A1, A2...** An and let **r** denote the radix( for example **r=10** for decimal digits, **r=26** for English letters and **r=2** for hits). If **A1** is the largest number then **A!** Can be represented. Then **radix sort** require **s** passes. In passes, each element is compared with the bucket elements.

So the **radix sort** requires the total comparison **f(n)** of: **F(n) < = r x s x n**

### Worst case

In the worst case **s = n** so **F(n) = O(n2)**

### Best case

In the best case **s = logn** so **f(n) = (nlogn)**

### Average case

It is very hard to define the time complexity. Because it will depend on the choice of the radix **r** and also the number of a digit on largest elements (i.e number of passes) but on an average (**log n**) comparison is required so **f(n) = O(nlogn)**

## Advantages of Radix Sort

The following are the advantages of radix sort:

- It is implemented in Java, it would be faster than quicksort or heap.
- It is stable because it preserves existing order of equals keys.
- It is good on small keys.

## Disadvantages of Radix Sort

The following are the disadvantages of radix sort:

- It is not efficient on very long keys because the total sorting time is proportional to key length and to the number of items to sort.
- We have to write an unconventional compare routine.
- It requires fixed size keys and some standard way of breaking the keys to pieces.

## Radix Sort Example

To illustrate the radix sort consider the following array with 7 elements

42, 133, 7, 23, 74, 670, 49

In this array, the biggest elements are 670 and the number of digits is 3, so 3 passes are required to sort the array. Read the elements and compare the first position (2 is in the first position of 42) digits with the digits of the buckets and place it

Now read the elements from left to right and the bottom to the top of the bucket and place it in an array for the next pass. Read the array elements and compare the second position (4 is in the second position of the elements 042) digit with a number of the bucket and place it.

Again read the element from left to right and from bottom to top to get an array for the third pass. (0 is in the first position of 042) compare the third position digit in each element with the budget digit and place it wherever it matches.

**Now the sorted array is 7 , 23, 42, 49, 74, 133, 670.**

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Dynamic Programming (Components, Applications and Elements)
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Sieve of Eratosthenes to find prime numbers
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Jump Search Implementation using C++
- Optimal Merge Pattern (Algorithm and Example)
- Introduction to Greedy Strategy in Algorithms
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Graph coloring problem's solution using backtracking algorithm
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- P and NP problems and solutions | Algorithms
- Travelling Salesman Problem
- 2 – 3 Trees Algorithm
- Kruskal's (P) and Prim's (K) Algorithms
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Midpoint Circle Algorithm
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking

Comments and Discussions!