Learn how to implement a radix sort algorithm in this free chapter from our new book, Data Structures and Algorithms in Swift!
Hi, great example. So would this be a faster and more efficient way to sort an array compared to just using the built-in sort() in swift? Like if the array was bigger?
It depends on the data. First, radix sort can only be used on types have positional notation (i.e. integers).
Radix sort outperforms Swift’s built in sort if the data is more or less uniformly distributed. The best case scenario for radix sort is a very massive array of single digit integers. It becomes a bit slower the instant a 2 digit number appears in the array; and gets worse as higher and higher digit numbers come into play.
Swift’s sort function has a time complexity of O(n log n), and radix sort has a time complexity of O(n).
You should be weary of the hidden cost of radix sort. It needs to allocate buckets every pass, which can take some time. For small inputs, allocating the buckets may cost more time than using a sort that doesn’t allocate extra resources.
In general, radix sort would probably be faster as data size grows. It’s also important to note that Swift’s sort method can sometimes specialize to perform at O(n) for small arrays that are in already sorted or nearly sorted order (by internally switching over to insertion sort).
TL;DR = It depends on your data