Radix Sort

Overview

Radix Sort dates all the way back to 1887 to the work of Herman Hollerith on tabulating machines. It is a non-comparative sorting algorithm which groups integer keys based on individual digits which share the same significant position and value. However, since integers can be used to represent strings and characters, its use isn’t limited to pure integer data types.

Concept

Algorithmic Complexity

Big-O

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Radix SortArrayO(nk)O(nk)O(nk)O(n+k)

 

Implementation

Java Implementation

Coming soon!

References

Wikipedia: Radix sort

 

<- back