CODEWITHSUNDEEP
c++algorithmsorting
Serge Rogatch
Serge Rogatch

Reputation: 15020

Is std::sort optimized for sorting small amount of items too?

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++?

Upvotes: 5

Views: 2602

Answers (3)

Serge Rogatch
Serge Rogatch

Reputation: 15020

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);
}

Upvotes: 3

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

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.

Upvotes: 3

Jepessen
Jepessen

Reputation: 12415

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

Upvotes: 0

Related Questions