Hacker News

points by MichaelDickens 3 days ago | 0 comments

There are realistic situations where galactic O(n) sorting algorithms exist, right? 32-bit integers can be sorted in O(n) using 2^32 words of memory, using bucket sort[1].

If objects have a maximum size of 4 GB (= 2^35 bits), then arbitrary objects can be sorted in O(n) using 2^2^35 bits of memory.

[1] https://en.wikipedia.org/wiki/Bucket_sort

[–] yyyk 3 days ago

Right, that's why I wrote "a generic sorting algorithm". Your case adds the integer limit which allows it to avoid O(nlogn) minimum.

[–] adrianN 3 days ago

You can use Radix sort https://en.wikipedia.org/wiki/Radix_sort to lower the memory requirement for limited bit-width integers. But there are more practical o(n log n) methods for sorting integers.

[–] adgjlsfhk1 3 days ago

Well optimized radix sorts are actually pretty fast (assuming you have the proper fallbacks to quicksort/insertion sort to deal with medium/small sizes)