What is the fastest sorting algorithm for a small number of integers?

Question

I am wondering what the fastest algorithm would be for this. I have 8 integers between 0 and 3000 and I need to sort them. Although there are only 8 integers, this operation will be performed millions of times.

Answer 1

Here is an implementation of an odd-even merge sort network in C99 (sorry for the "wrong" language):

#define CMP_SWAP(i, j) if (a[i] > a[j])              \
    { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }

void sort8_network(int *a)
{
    CMP_SWAP(0, 1); CMP_SWAP(2, 3); CMP_SWAP(4, 5); CMP_SWAP(6, 7);
    CMP_SWAP(0, 2); CMP_SWAP(1, 3); CMP_SWAP(4, 6); CMP_SWAP(5, 7);
    CMP_SWAP(1, 2); CMP_SWAP(5, 6); CMP_SWAP(0, 4); CMP_SWAP(1, 5);
    CMP_SWAP(2, 6); CMP_SWAP(3, 7); CMP_SWAP(2, 4); CMP_SWAP(3, 5);
    CMP_SWAP(1, 2); CMP_SWAP(3, 4); CMP_SWAP(5, 6);
}

I timed it on my machine against insertion sort

void sort8_insertion(int *a)
{
    for (int i = 1; i < 8; i++)
    {
        int tmp = a[i];
        int j = i;
        for (; j && tmp < a[j - 1]; --j)
            a[j] = a[j - 1];
        a[j] = tmp;
    }
}

For about 10 million sorts (exactly 250 times all the 40320 possible permutations), the sort network took 0.39 seconds while insertion sort took 0.88 seconds. Seems to me both are fast enough. (The figures inlcude about 0.04 seconds for generating the permutations.)

Answer 2

The fastest would be to simply write a lot of if statements to compare them to determine their exact order. That will remove the overhead that any sorting algoritm has.

Answer 3

For only 8 integers and given that the range is much greater than 8, insertion sort is probably the best. Try it to start with, and if profiling indicates that it's not the bottleneck then leave it.

(Depending on many factors, the cutoff point at which quick-sort becomes better than insertion sort is usually between 5 and 10 items).

Answer 4

The fastest way is a sorting network implemented in hardware. Barring that, the fastest way is determined only by measuring. I'd try

• std::sort,
• pigeonhole (bucket) sort with reuse of the buckets,
• a bunch of if statements, and
• insertion sort

in that order, because it's the easiest-to-hardest order (try to get insertion sort right the first time...) until you find something that's maintainable once the constant eight turns out to have the value nine.

Also, bubble sort, selection deserve and shell sort deserve notice. I've never actually implemented those because they have bad rep, but you could try them.

Answer 5

Years later) for up to 32 inputs, see the Sorting network generator. For 8 inputs, it gives 19 swaps, like Sven Marnach's answer:

o--^--^--------^--------------------------o
   |  |        |
o--v--|--^--^--|--^--^--------------------o
      |  |  |  |  |  |
o--^--v--|--v--|--|--|--^--------^--------o
   |     |     |  |  |  |        |
o--v-----v-----|--|--|--|--^--^--|--^--^--o
               |  |  |  |  |  |  |  |  |
o--^--^--------v--|--v--|--|--|--v--|--v--o
   |  |           |     |  |  |     |
o--v--|--^--^-----v-----|--|--|-----v-----o
      |  |  |           |  |  |
o--^--v--|--v-----------v--|--v-----------o
   |     |                 |
o--v-----v-----------------v--------------o


There are 19 comparators in this network,
grouped into 7 parallel operations.

[[0,1],[2,3],[4,5],[6,7]]
[[0,2],[1,3],[4,6],[5,7]]
[[1,2],[5,6],[0,4],[3,7]]
[[1,5],[2,6]]
[[1,4],[3,6]]
[[2,4],[3,5]]
[[3,4]]

Answer 6

The following citation from Bentley et al., Engineering a sort function could be interesting here:

Various improvements to insertion sort, including binary search, loop unrolling, and handling n=2 as a special case, were not helpful. The simplest code was the fastest.

(Emphasis mine.)

This suggests that plain insertion sort without fancy modifications would indeed be a good starting point. As Peter has noted, eight items is indeed a bit tricky because that lies squarely in the range which usually marks the cut-off between insertion sort and quicksort.

Answer 7

I ran a library of sort algorithms against all permutations of {0, 429, 857, 1286, 1714, 2143, 2571, 3000}.

The fastest were:

name                                time   stable in-place
AddressSort                         0.537   No      No
CenteredLinearInsertionSort         0.621   Yes     No
CenteredBinaryInsertionSort         0.634   Yes     No
BinaryInsertionSort                 0.639   Yes     Yes
...
QuickSort                           0.650   No      Yes
...
BubbleSort                          0.802   Yes     Yes

For more on AddressSort see http://portal.acm.org/citation.cfm?id=320834

Answer 8

A good source for comparing sorting algos is http://www.sorting-algorithms.com/. Note that even the initial order status affect the results. But anyway for 8 integers even a plain bubble sort should do the job.

Answer 9

For positive integers, the fastest sort is known as abacus sort- it's O(n)

http://en.wikipedia.org/wiki/Abacus_sort

If you only have a very few items, then it's unlikely that you will notice any performance difference from choosing any particular algorithm.

Answer 10

For very small numbers of ints, bubble sort can be very fast. Bubble sort with numerical comparisons can be written with a very low overhead and for small n, the actual speed differences between O(n log n) and O(n^2) washes out.

Answer 11

Have you profiled your code to show that the sort is a bottleneck? If it isn't a bottleneck, then speeding it up won't buy you much. Sorting eight short integers is pretty fast.

In general, std::sort() will be faster than anything you can write, unless you are a real sorting guru.

Answer 12

For integers, you could try radix-sort. It's O(N).