Hacker News Reader

Comment by pfdietz | Hacker News Reader

Interestingly, radix sort can also lexicographically sort a collection of strings over a fixed alphabet in time O(sum of sizes of strings). It's not necessary to assume all the strings have the same length.

View on HN

Exactly. Radix sort isn't really linear. It is O(N * M) where N is the size of the collection and M is the number of possible items in the collection. If the number of possible items is fixed (like fixed-size integers) then it is effectively linear. However you can do this with strings just the same way.

You can also say comparison sorts are O(N * ln N * M) where N is the size of the collection & M is the cost of comparison (eg string length for comparing strings)

But instead we say it requires O(N * ln N) comparisons

If you read the actual proofs, they count comparisons, not operations, when they arrive at O(nlogn). More advanced material analyses algorithms on random access machines with some fixed word size for cases where you can't assume that comparisons are constant time operations, or specialize for the data type, e.g. numbers, where you sometimes don't need o(n log n) comparisons at all (like with radix sort).

The model I usually consider is a RAM where the word size is ~ logn bits. This seems closest to real computers.

I find this article pretty insightful for thinking about algorithms that involve lots of memory: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

That article's discussion on HN (6 years ago!) was also quite interesting:

https://news.ycombinator.com/item?id=12383012

M = string length and M = number of different possible values are very, very different. One is the exponential of the other.

Why M? The whole point of radix sort is to do the comparisons binary digit by digit so that the total number becomes O(N * log(M)).

Oops, you are right. I was thinking the entropy/bits of the possibilities but accidentally wrote number.

Reply on news.ycombinator.com