Quickest sorting algorithm for sorting a low number of integers

Question

I am making a program on my spare time that I want to run as quickly as possible. The program is written in C.

A large set of the procedures operate on pointers to 7 integers that are sorted by their numerical values from high to low.

Up to this point I have used the library function "qsort" to sort my integers. Now when I have finished the rest of the application I want to replace my call to qsort with something quicker.

I want a sorting algorithm to sort a fixed number of 7 integers as fast as possible. Please tell me what you would use and why you think it is best.

• I have read about the Big O notation and from what I have found out it only measures how long the algorithm will take according to the number of elements it needs to sort. Does the Big O notation really matter when I only need to sort 7 elements? Can O(n * log n) be faster than a O(n ^ 2) in this case?

• "radixsort" seems like a good choice to me but I want to get your opinions too.

The sorting algorithm will be used millions of times and during that time the user of the program has to wait. My program runs almost 10 times slower since I started using qsort (before that I measured it using a hard-coded array).

• Rotem: Big O notation does not measure performance, it measures expected changes in performance in relation to changes in the size of the data set. In your case, the Big O complexity of the algorithm is of very little importance.
• JensG: A good rule of thumb is "Given 10 elements or less, next to any algorithm performs well". Maybe Bogosort will be a bit at the slow end. So no, the Big O notation does not really matter when sorting 7 elements, except if you are going to sort 5 million times seven arbitrarily chosen elements.
• kdgregory: What were you using before qsort()? If your program runs 10x slower after changing that one thing you should switch back to whatever it was.
• wefwefa3: @kdgregory Sorry for the confusion. I tested my code in a loop with a hard-coded array that already was sorted.
• wefwefa3: @Rotem. Thank you for your response. I would still like to know if there is a specific one that is better suited than others because sorting is done so frequently in this program.

Answer 1

Take a look at this neat implementation of sorting six integers. According to sorting networks, 16 comparisons are required to sort 7 integers. Here is the code for seven integers:

 static int sort7(int *d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
 SWAP(1, 2);
 SWAP(3, 4);
 SWAP(5, 6);
 SWAP(0, 2);
 SWAP(3, 5);
 SWAP(4, 6);
 SWAP(0, 1);
 SWAP(4, 5);
 SWAP(2, 6);
 SWAP(0, 4);
 SWAP(1, 5);
 SWAP(0, 3);
 SWAP(2, 5);
 SWAP(1, 3);
 SWAP(2, 4);
 SWAP(2, 3);
#undef SWAP
}

Note that I did not test the code!

• wefwefa3: My program runs twice as fast after switching to this. What used to take the program 10.399s to do with qsort now it only takes 4.891s. :)
• user40980: @user3787875 you might enjoy reading more about sorting networks - there are some interesting bits in there.
• wefwefa3: @MichaelT Thank you. It was very fun to read and I learned alot!
• user204677: My brain almost exploded looking at this until I realized that SWAP does a comparison. Neat inlined code anyway!