Re:Linear O(N) sorting with Radix Sort (2000)
by contravariant on Tuesday February 01, 2022 @07:42AM
(#30161704)
Somehow the article posits you need to check if the list is already sorted to support multiple passes, but this version of radix sort is designed to be stable which is all you need.
And technically checking if the list is already sorted is mostly faster because of caching, in theory radix sort could read each byte exactly once.
And technically checking if the list is already sorted is mostly faster because of caching, in theory radix sort could read each byte exactly once.