Knowledge Base > Algorithm > Sorting
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.
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
Usually, The stable sort in step two is usually done using bucket sort or counting sort, which also run at linear time.
Like counting sort, the LSB radix sort does not run in place, that is, more memory space is required.
A LSB radix sort is stable (by definition).
The sorting mechanism I used for LSB Radix Sort is Counting Sort.