What is the fastest possible way to sort an array of 7 integers?

Question

This is a part of a program that analyzes the odds of poker, specifically Texas Hold'em. I have a program I'm happy with, but it needs some small optimizations to be perfect.

I use this type (among others, of course):

  type
    T7Cards = array[0..6] of integer;

There are two things about this array that may be important when deciding how to sort it:

1. Every item is a value from 0 to 51. No other values are possible.
2. There are no duplicates. Never.

With this information, what is the absolutely fastest way to sort this array? I use Delphi, so pascal code would be the best, but I can read C and pseudo, albeit a bit more slowly :-)

At the moment I use quicksort, but the funny thing is that this is almost no faster than bubblesort! Possible because of the small number of items. The sorting counts for almost 50% of the total running time of the method.

EDIT:

Mason Wheeler asked why it's necessary to optimize. One reason is that the method will be called 2118760 times.

Basic poker information: All players are dealt two cards (the pocket) and then five cards are dealt to the table (the 3 first are called the flop, the next is the turn and the last is the river. Each player picks the five best cards to make up their hand)

If I have two cards in the pocket, P1 and P2, I will use the following loops to generate all possible combinations:

for C1 := 0 to 51-4 do
  if (C1<>P1) and (C1<>P2) then
     for C2 := C1+1 to 51-3 do
       if (C2<>P1) and (C2<>P2) then
         for C3 := C2+1 to 51-2 do
           if (C3<>P1) and (C3<>P2) then
             for C4 := C3+1 to 51-1 do
               if (C4<>P1) and (C4<>P2) then
                 for C5 := C4+1 to 51 do
                   if (C5<>P1) and (C5<>P2) then
                   begin
                     //This code will be executed 2 118 760 times
                     inc(ComboCounter[GetComboFromCards([P1,P2,C1,C2,C3,C4,C5])]);
                   end;

As I write this I notice one thing more: The last five elements of the array will always be sorted, so it's just a question of putting the first two elements in the right position in the array. That should simplify matters a bit.

So, the new question is: What is the fastest possible way to sort an array of 7 integers when the last 5 elements are already sorted. I believe this could be solved with a couple (?) of if's and swaps :-)

Answer 1

Use a sorting network, like in this C++ code:

template<class T> 
inline void sort7(T data) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
//DD = Define Data, create a local copy of the data to aid the optimizer.
#define DD1(a)   register auto data##a=*(data+a);
#define DD2(a,b) register auto data##a=*(data+a);register auto data##b=*(data+b);
//CB = Copy Back
#define CB1(a)   *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(3,4) SORT2(3,4)
  DD2(5,6) SORT2(5,6)
  DD1(0) SORT2(0,2)
  SORT2(3,5) 
  SORT2(4,6) 
  SORT2(0,1)
  SORT2(4,5) 
  SORT2(2,6) CB1(6)
  SORT2(0,4) 
  SORT2(1,5)
  SORT2(0,3) CB1(0) 
  SORT2(2,5) CB1(5)
  SORT2(1,3) CB1(1) 
  SORT2(2,4) CB1(4)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Use the function above if you want to pass it an iterator or a pointer and use the function below if you want to pass it the seven arguments one by one. BTW, using templates allows compilers to generate really optimized code so don't get ride of the template<> unless you want C code (or some other language's code).

template<class T>
inline void sort7(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5, T& e6) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(3,4) SORT2(3,4)
  DD2(5,6) SORT2(5,6)
  DD1(0) SORT2(0,2)
  SORT2(3,5)
  SORT2(4,6)
  SORT2(0,1)
  SORT2(4,5)
  SORT2(2,6) CB1(6)
  SORT2(0,4)
  SORT2(1,5)
  SORT2(0,3) CB1(0)
  SORT2(2,5) CB1(5)
  SORT2(1,3) CB1(1)
  SORT2(2,4) CB1(4)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Answer 2

For a very small set, insertion sort can usually beat quicksort because it has very low overhead.

WRT your edit, if you're already mostly in sort order (last 5 elements are already sorted), insertion sort is definitely the way to go. In an almost-sorted set of data, it'll beat quicksort every time, even for large sets. (Especially for large sets! This is insertion sort's best-case scenario and quicksort's worst case.)