Fastest unconditional sort algorithm

Question

I have a function, which can take two elements and return them back in ascending order:

void Sort2(int &a, int &b) { 
  if (a < b) return; 
  int t = a; 
  a = b; 
  b = t; 
}

what is the fastest way to sort an array with N entries using this function if I am not allowed to use extra conditional operators? That means that whole my program should look like this:

int main(){
  int a[N];
     // fill a array

  const int NS = ...; // number of comparison, depending on N.
  const int c[NS] = { {0,1}, {0,2}, ... }; // consequence of indices pairs generated depending on N.
  for( int i = 0; i < NS; i++ ) {
    Sort2(a[c[i][0]], a[c[i][1]]);
  }
     // sort is finished
  return 1;
}

Most of the fast sort algorithms use conditions to decide what to do. There is bubble sort of course, but it takes M = N(N-1)/2 comparisons. This is not the optimum, for instance, with N = 4 it takes M = 6 comparison, meanwhile 4 entries can be sorted with 5:

Sort2(a[0],a[1]);
Sort2(a[2],a[3]);
Sort2(a[1],a[3]);
Sort2(a[0],a[2]);
Sort2(a[1],a[2]);

---

Answer 1

The standard approach is known as Bitonic Mergesort. It is hella efficient when paralellized, and only slightly less efficient than conventional algorithms when not parallelized. Bitonic mergesort is a special kind of a wider class of algorithms known as "sorting networks"; it is unusual among sorting networks in that some of its reorderings are in reverse order of the desired sort (though everything is in the correct order once the algorithm completes). You can do that with your Sort2 by passing in a higher array slot for the first argument than the second.