5

There is an algorithm to sort 5 items in 7 comparisons: Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons Does std::sort() use that algorithm if it is called for 5 items? Can this algorithm be extended to 7 items? What is the fastest algorithm for sorting 7 integers in C/C++?

Community
  • 1
  • 1
Serge Rogatch
  • 13,865
  • 7
  • 86
  • 158
  • 1
    You know that there are a lot implementations for std::sort? There is no "general" design description how a concrete implementation will do the job. Simple answer: Look in the code! std::sort is header only code, so simply look there! – Klaus Jul 17 '15 at 09:01
  • 2
    While it's permitted by the standard, it's certainly not required, and I would guess that no implementations actually do this for 2 reasons: (1) Every call to `std::sort()` would need to check for this special case (and presumably other small special cases -- unless you think it's important to sort 5-7 items but not 4 items or 8 items), and these tests are probably as expensive as the comparisons saved; (2) it's extra effort for (usually) tiny gain (in fact the extra code needed for all the special cases keeps other code out of cache, so it may cause a net slowdown). – j_random_hacker Jul 17 '15 at 09:03
  • 1
    @j_random_hacker, it could use a table of special function pointers, so that if the number of items to sort is `n`<10 then `f[n]` is called, otherwise general (merge-sort) implementation is used. – Serge Rogatch Jul 17 '15 at 09:13
  • 1
    If you can get your hands on "The Art of Programming" by Knuth, there is a chapter on _optimal_ sorting algorithms (minimum comparisons) for small number of elements (Chapter 5, "Optimum Sorting" if I remember correctly) –  Jul 17 '15 at 09:15
  • @SergeRogatch but will that actually be faster and worth the complexity? Look at the comments on the question you linked, quick/merge sort only got 8 comparison anyways and the one specialized for the input size got 7 comparisons, that's not worth it in my opinion for the complexity you're adding with all the special cases. Also sorting such small sizes are near instantaneous anyways, hardly gonna be a bottleneck. – AliciaBytes Jul 17 '15 at 09:16
  • @SergeRogatch: That would certainly be O(1) time, but I suspect that the pointer indirection involved will wind up making this actually much slower in the common cases where the comparison function is fast (e.g., comparing `int` values). Maybe CPU branch predictors have advanced to the point where they can handle this quickly now, but ~10 years ago when I was keen on cycle-squeezing, tables of function pointers were nearly always a net loss (despite the appealing elegance!) – j_random_hacker Jul 17 '15 at 09:19
  • PS. In "Elements of Programming" by Stepanov and McJones there is also C++ code for minimum comparison "sorting" of up to 5 elements. Implementing the same for more than 5 is left as an exercise (I don't have the book right now so I might be wrong on the details). –  Jul 17 '15 at 09:23
  • 1
    @SergeRogatch: OTOH I have to say that one advantage of special-casing small arrays is that you could write code that implements a *sorting network* that sorts them "blindly", i.e., with a fixed sequence of compare-and-possibly-swap operations. Because there are no dependencies *between* these operations, I would expect this to be faster than ordinary sorting algorithms (which have to pray to the branch predictor for good performance) if the sorting network doesn't need too many more CAPS operations than the regular sort needs compares+swaps. – j_random_hacker Jul 17 '15 at 09:29
  • 1
    @RaphaelMiedl, a few saved CPU cycles per sorting worth the effort if sorting of 7 items is performed billions of times. – Serge Rogatch Jul 17 '15 at 09:31
  • 1
    [Fastest sort of fixed length 6 int array](http://stackoverflow.com/q/2786899/995714), [What is the fastest sorting algorithm for a small number of integers?](http://stackoverflow.com/q/4770651/995714) – phuclv Jul 17 '15 at 09:39
  • @Klaus, by looking into implementation on MSVC++2013, I figured out that insertion sort is used for 7 items. – Serge Rogatch Jul 18 '15 at 08:14
  • Related: Is there a boost or other library that provides a nice generic fixed-size sort? As in `template > void sort_n(RandomIt beg, Comp comp = Comp{})`. It could at its discretion fall back to `std::sort` for large `N`, but for `N <= 1` it wold be a NOP. (Similarly, I could see someone wanting `small_sort` which takes an iterator pair, switches on `std::distance(beg, end)`, to jump to optimized small cases first.) – Ben Sep 08 '21 at 16:31

3 Answers3

3

It is not a part of the standard if std::sort should try to perform as few as possible comparisons for small sizes. Different implementations may do that but this will depend on the library you are using.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
3

Looking at the code of std::sort in STL of MSVC++2013, it uses insertion sorting for 7 items.

Some comments suggested to use sorting networks. Sorting networks for small number of items (up to 32) can be generated here. Particularly, for sorting 7 items without parallelism the fastest algorithm seems this . According to the experiments here, the fastest SWAP macro implementation is:

#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { \
    const int a = min(d[x], d[y]); \
    const int b = max(d[x], d[y]); \
    d[x] = a; d[y] = b; }

The sorting-network code for 7 items would be:

template<typename T> void sort7(T* d)
{
    SWAP(0, 1);
    SWAP(2, 3);
    SWAP(0, 2);
    SWAP(1, 3);
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(4, 6);
    SWAP(5, 6);
    SWAP(0, 4);
    SWAP(1, 5);
    SWAP(1, 4);
    SWAP(2, 6);
    SWAP(3, 6);
    SWAP(2, 4);
    SWAP(3, 5);
    SWAP(3, 4);
}
Community
  • 1
  • 1
Serge Rogatch
  • 13,865
  • 7
  • 86
  • 158
0

Algorithm is dependent on implementation. Usually quicksort algorithm is used, that's O(n log n).

Jepessen
  • 11,744
  • 14
  • 82
  • 149
  • 5
    Actually usually introsort(a hybrid between several sorting algorithms) is used and it dictates the usage of insertion sort for small sizes. Also quick sort has O(n*log(n)) **expected** complexity – Ivaylo Strandjev Jul 17 '15 at 09:02
  • quick sort can't be used because it's not O(nlogn) worst case which is required – RiaD Jul 17 '15 at 09:08
  • "The GNU Standard C++ library uses a hybrid sorting algorithm: first introsort is performed, to a maximum depth given by 2×log2 n, where n is the number of elements, followed by an insertion sort on the result." (https://en.wikipedia.org/wiki/Introsort#Implementations) – SChepurin Jul 17 '15 at 09:30
  • 2
    @RiaD: Your statement is inaccurate. Quicksort *can* be implemented with O(n log(n)) worst case by using a suitable algorithm for calculating the pivot. It is just not commonly implemented that way because this would slow down the average case (and because it's a bit complicated). The same goes for stability, BTW: possible but usually not done for performance reasons. – Arne Vogel Jul 17 '15 at 14:04