Tuesday, 15 September 2015

Faster than quicksort, merge sort, insert sort...

Sorting networks. It turns out that if you have a fixed number of items to sort, there is a much faster approach than the general sorting algorithms.

eg. you regularly have exactly 6 items to sort. You use a predefined series of compares and swaps, and afterwards you can be certain that the items are in order.

From the Wikipedia page:
Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. 

No comments:

Post a Comment