Sort algorithm with fewest number of operations

Question

What is the sort algorithm with fewest number of operations? I need to implement it in HLSL as part of a pixel shader effect v2.0 for WPF, so it needs to have a really small number of operations, considering Pixel Shader's limitations. I need to sort 9 values, specifically the current pixel and its neighbors.

Answer 1

Knuth has done some work on finding optimal sorting algorithms. However even for just five elements the algorithm with the smallest number of comparisons is very complicated to implement.

I suggest instead of trying to find the optimal algorithm that you try to find one that is simple to implement and good enough for your needs. If you have access to a standard sorting algorithm try using that first. If not then you could use an insertion sort or merge sort to keep it simple and see if that is good enough for you.

Insertion Sort:

• Simple implementation
• Efficient for (quite) small data sets
• Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
• More efficient in practice than most other simple quadratic, i.e. O(n2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
• Stable, i.e. does not change the relative order of elements with equal keys
• In-place, i.e. only requires a constant amount O(1) of additional memory space
• Online, i.e. can sort a list as it receives it.

Answer 2

You either want to use Insertion sort or Radix sort. Here are some C++ implementations:

Radix Sort

void radix (int byte, long N, long *source, long *dest)
{
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ )
    count[((source[i])>>(byte*8))&0xff]++;

  index[0]=0;
  for ( i=1; i<256; i++ )
    index[i]=index[i-1]+count[i-1];
  for ( i=0; i<N; i++ )
    dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}

You need to call radix() four times, as it only works on one column.

Insertion Sort

void insertSort(int a[], int length)
{    
    int i, j, value;
    for(i = 1; i < length; i++)
    {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--)
            a[j + 1] = a[j];
        a[j + 1] = value;
    }
}