Sort a small number of items

Question

I often find myself in a situation where I want to sort a small number of elements. Little, I mean 3 or 4. I probably understood correctly that with such small sets of problems I would like to use some explicit or direct method, and not refer to the sort function. 2 is trivial, 3 elements are still pretty simple, but above 4 elements or so, and I'm starting to prefer the simplicity of just starting insertion sort.

How many elements can I expect the benefits of coding inline void sort_n(int *list) ? 4? 5? 6?

In this section, sorting an int array with 3 elements there are two solutions for sorting three elements. One has more comparisons, while the other minimizes comparisons, but is more difficult. On modern architecture, which will reach the top of speed?

Answer 1

Look at the sorting of networks.

A few links:
http://en.wikipedia.org/wiki/Sorting_network
http://www.cs.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html
Fastest fixed length type 6 int array

Answer 2

Was your application a profile and that turned out to be a bottleneck? Or are you trying to overestimate?

Bubblesort can also work very well. In particular, when your data is already sorted, this is actually optimal and will beat any merging tutorial or sorting heap. If you do not give complete restrictions (the cost of replacing elements, the requirements for stability, in place or not), no one can fully answer this question.

In any case, for the four elements it’s pretty obvious how to implement an efficient merge sort.

For odd (inferior 2) sizes, I find reverse insertion sorting to be a general optimization. Take a look at the Javas collation implementation. I believe that it already has such a small array optimization. Have you verified that the sorting procedure that you would call no longer performs such optimizations?

Answer 3

All answers to optimization questions should be preceded by a warning that you should profile and optimize bottlenecks, therefore: be sure to do this.

In the spirit of C / C ++, I now trust you to do this and answer your question.

You define the answer to your question by iterative profiling.

Write template <int N> inline void sort_n(int * list) , which defaults to std lib sorting. Use this template when necessary in your code. Then write specialized patterns for the smallest case of N, for which you do not yet have a specialization. After writing this specialization, profile your program and see if you can achieve a significant performance boost. If you are making a performance gain that you judge significant, repeat. After you write a specialization and do not get much, stop.

Answer 4

For any reasonable number of elements, you always benefit from performance by explicitly encoding comparisons. However, sorting so few items takes so little time, it rarely matters which method you use anyway.

The threshold at which you will not get any performance benefit is when you get so much code that it will no longer enter the processor cache, therefore, when the threshold will differ depending on which processor you use on it.

You should also consider how you will test such code. The more code you have, the harder it will be to make sure that it does not work.

Answer 5

First you need to profile your application to determine if this optimization is worth it. I suspect this will not happen. Standard library functions (or enhancements) will almost certainly be your best choice for sorting.

Answer 6

Insertion sorting and bubble sorting are usually used for small data.

I believe insertion sorting is preferable, referring to these 2 Wikipedia texts:

quicksort implementation uses insertion sorting for arrays below a certain threshold

and

The Bubble variety also interacts poorly with modern processor hardware. This requires at least twice as many records, such as insertion sorting, twice as many cache misses, and asymptotically more incorrect predictions. Astrachan's string sorting experiments in Java show that bubble size is about 5 times slower than insert sorting, and 40% slower than sorting sorting.

As always, you should profile if you are really concerned about speed.

Answer 7

I am told that standard library sortings have optimized cases for small n - I never tried to test it.