3 ms·
In general asymptotic analyses (including the well-known O(n log n) bound for comparison based sort) assume a model where operations like compare, swap, arithme
by jstimpfle 8y ago
In general asymptotic analyses (including the well-known O(n log n) bound for comparison based sort) assume a model where operations like compare, swap, arithmetics, etc. are constant-time. So they only work for bounded integers, practically speaking.
If you want to know for the general case, you need to adapt your machine model and redo the analysis. Operations will likely be not constant-time but something like log(x) where x is the size of the integer at hand. But of course, that's up to you and what you want to do and how you build your machine.
- KirinDave 8y agoI think this isolation is done to critique the algorithm in question in isolation of any underlying structure. What's cool about Discrimination sort is that it does, in fact, can give these linearity guarantees for most kinds of data a computer can represent, including things like strings which have variable length or structs. There are some caveats there, but they're easy enough to work with that nearly every default structure in haskell as seen here: http://hackage.haskell.org/package/discrimination-0.3/docs/Data-Discrimination-Sorting.html#g:1 http://hackage.haskell.org/package/discrimination-0.3/docs/D... Note particularly the instance for [a], and that you can extend it to something like Data.Text's codepoints (and this would work out of the box with something like ByteString's chunked form).