3.9.9 Radix Sort

Knowledge Base > Algorithm > Sorting

Overview

Radix Sort is a selection-based sorting algorithm that sorts integers by processing each digits. The idea of Radix Sort was originally used to sort punched cards to determine which place had been punched. There are two kinds of Radix Sort, starting sorts either from least significant big (LSB), or most significant bit (MSB). The Radix Sort performs nearly at linear time, in the best case, depending on average length (or number of digits) of each numbers to be sorted. A good practice of Radix Sort is to sort a group of binary digit, usually represented with strings of 0s and 1s.

Algorithm

Pseudocode

Radix-Sort(A)

1 for i ← 1 to d 2 do use a stable sorting algorithm to sort array A on digit i

The LSB Radix Sort operates at O(n⋅k), where n is the number of element to be sorted and k is the average length of each number. The algorithm performs as follow

• Take the first digit (LSB) of each number.
• Sort the numbers based on that digit, while keeping the original order of keys.
• Repeat those two process to next digits.

Time Complexity

Usually, The stable sort in step two is usually done using bucket sort or counting sort, which also run at linear time.

Space Complexity

Like counting sort, the LSB radix sort does not run in place, that is, more memory space is required.

Stability

A LSB radix sort is stable (by definition).

Source Code

The sorting mechanism I used for LSB Radix Sort is Counting Sort.

• LSB Radix Sort (C)
  
  
  

Related Topics

• Counting Sort
• Bucket Sort