Re:Bead sort: faster than O(N log N) sort
by Liron on Monday June 22, 2009 @12:42AM
(#668246)
"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.
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.