4 ms·
There are "sorting algorithms" faster than O(n log n); that limitation only applies to comparison sorts. These typically have complexity depending on the keysp
by amalcon 17y ago
There are "sorting algorithms" faster than O(n log n); that limitation only applies to comparison sorts. These typically have complexity depending on the keyspace (for example, counting-sort has linear complexity in whichever is greater, the size of the input list or the keyspace).
They're also typically kind of useless, as in this example, because we rarely care to sort an arbitrary list of integers with no metadata. Radix-sort is a rare exception, in that it can easily be modified to carry metadata, hence people actually using it in some applications.
- Liron 17y ago"They're also typically kind of useless, as in this example, because we rarely care to sort an arbitrary list of integers with no metadata." O(n) sorting algorithms are only impractical if the size of the keyspace dwarfs the number of elements to be sorted. In general a key is a variable-length string of bits, which makes for an exponentially-sized keyspace, so you want to stick with comparisons of element pairs. But "metadata" has nothing to do with it. The last bead in each BeadSort row can contain a sticker with some metadata. That kind of trick generalizes to all sorts.
- praptak 17y ago"The last bead in each BeadSort row can contain a sticker with some metadata." Wrong. The beads in columns remain in the original order (not sorted) and so would these stickers.