News for hackers. Stuff that matters.
Re:Linear O(N) sorting with Radix Sort (2000) by saurik on Tuesday February 01, 2022 @08:11AM (#30161917)
The bottom of this article links to an article by Michael Herf (of f.lux fame, but also having had developed Picassa) on his radix sort optimizations. I considered these two articles to be absolutely critical to my understanding of algorithms back 20 years ago, when I was finally transitioning to "more complex" development while working with/for Jake Cannell (who had worked under Herf and was paying close attention to Pierre). I came to believe that sorts that don't at least try to use don't use radix somewhere are somehow "missing the point" of algorithmic design.

A decade later, while working on Cydia--which has a complex problem of trying to provide efficient local operation of a federated "app store" on mobile devices, and was dealing with a need to sort tens of thousands of packages (and which had been very very slow with users getting increasingly angry at me refusing to centralized the service)--I ended up determining my biggest issue was the sorting process and turning to radix sort, using some experimentally-chosen offsets for radix passes, which I could use to "mostly sort" the data before switching to an insertion sort "fixup" pass (which could then use the fully-unicode-aware number-parsing magical comparator people are used to).

There are no comments on this comment yet.