Hacker News Reader

Comment by Radim | Hacker News Reader

Pierre Terdiman's "Radix sort revisited" for O(N) sorting (linear worst case!), from the same era:

http://www.codercorner.com/RadixSortRevisited.htm

> In every decent programmer’s toolbox lies a strange weapon called a Radix Sort. Where does it come from ? Who invented it ? I don’t know. As far as I can remember it was there, fast, easy, effective. Really effective. So unbelievably useful I’ve never really understood why people would want to use something else. The reasons ? Most of the time, they tell me about floats, negative values, and why their new quick-sort code rocks.

> Enough, I’m tired. Although the standard Radix Sort doesn’t work very well with floating point values, this is something actually very easy to fix. In this little article I will review the standard Radix Sort algorithm, and enhance it.

View on HN

It’s linear worst case if your values are unique (equivalent to hashing). If your values aren’t unique you will explode the search space on average to nlogn which is equivalent to open addressed hashing and thus iterating over sorted value set is going to take longer instead of sorting.

This is basically a bullshit post.

Curious to know more. Any sources?

The haskell 'discrimination' package provides quite general support for linear-time sorting, so it's certainly doable. (I don't recall exactly what the limitations about which value types it can handle, but it's reasonably general IIRC.)

There are references to a few papers in the README.

[0] https://hackage.haskell.org/package/discrimination

You can do linear time complexity as long as the keys you are sorting don’t duplicate. The moment they do you can’t bean nlogn. Logn is basically the overhead of the worst case probability when keys overlap.

Just to be clear if you keys don’t duplicate then you are not resolving a sorting problem per se. It’s just a degenerate case of the problem which is obviously easy to resolve.

I don't understand what you mean by duplicate here. Apply a Schwartzian Transform and there you go -- no duplicates.

the decorate sort undecorate is more expensive than the thing you're trying to save

That doesn't make sense. The Schwartzian Transform is linear time and cheap time-wise.

Btw, I'm surprised nobody has objections about constants. The constants for the type of stuff 'discrimination' does are (apparently) really bad. Like really bad.

^ The above was a bit sarcastic. I know you're talking about straight up performance, but the problem there wouldn't be the Schwartzian Transform.

Your assertion is contradicted by the article itself, which explains this point clearly. I.e., you're wrong.

Isn't it curious how often people with the most strongly voiced opinions ("bullshit post") are bullshitters themselves? There's some interesting dynamic going on, psychologically.

Have you read the article? It uses simple bubble sorting algorithm.

90% of it is discussing the instruction complexity of it. Which is not the same as “informational complexity”

Just to be clear it’s information-theoretically impossible to beat nlogn complexity.

Reply on news.ycombinator.com