rntz

    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.

rntz

9 years agodiscuss

I'm tempted to suggest

    (low / 2) + (high / 2)

but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop worrying about overflow altogether.

rntz

9 years agodiscuss

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.

rntz

10 years agodiscuss

Chez is known for being very fast, and for using state-of-the-art compiler technology.