4 ms·

The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.

• KirinDave 9y ago
  Right, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions. I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'm still working through the papers, the base of that chain is like 86 pages long! This search fallacy has been corrected. I'm mentioning one that hasn't.
  • rntz 9y ago
    Huh, is this the stuff you're talking about: http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf https://www.youtube.com/watch?v=sz9ZlZIRDAg https://hackage.haskell.org/package/discrimination I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.
    • KirinDave 9y ago
      Yes that is it. And it's really a variation on radix sort as well. They're all in the same general family. I can't believe I got down voted for this thread. What does it take? I guess I should just post it.
      • deleted 9y ago
        [deleted]
      • justin66 9y ago
        Given how few of those posting tonight appeared to understand the import of what Joshua Bloch wrote, I wouldn't take it personally. I'm slightly shocked by it, but I wouldn't take it personally...
        • KirinDave 9y ago
          I did post it, I even said provocatively, "O(n) general sort" in the title. Sadly the point gods were not kind.
    • deleted 9y ago
      [deleted]