Sorting small numbers of elements

Question

I am often finding myself in a situation where I want to sort a small number of elements. By small, I mean 3 or 4. I am probably correct in thinking that with such small problem sets I would want to use some type of explicit or direct method rather than invoking a sort function. 2 is trivial, 3 elements is still pretty simple but above 4 items or so and I'm starting to prefer the simplicity of just running insertion sort.

Up to how many elements can I expect a benefit to coding up a inline void sort_n(int *list)? 4? 5? 6?

In this topic, sorting int array with only 3 elements, there are two solutions for sorting 3 elements provided. One has more comparisons while the other minimizes comparisons but is more complicated. On a modern architecture, which would come out on top for speed?

Answer 1

Have a look at sorting networks.

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

Answer 2

Did you profile your application and this turn out to be a bottleneck? Or are you trying to overoptimize?

Bubblesort can work very well, too. In particular, when your data is already sorted, it actually is optimal and will beat any textbook merge or heap sort. Unless you give the full constraints (cost of swapping elements, stability requirements, in-place or not...) nobody can answer this fully.

Anyway, for four elements it is rather obvious how to implement an efficient merge sort inline.

For odd (non-power of 2) sizes I belive that backwards insertion sort is a common optimization. Have a look at Javas sorting implementation. I believe it has such a small array optimization already. Did you check that the sort routine you would have called doesn't already do this kind of optimizations?