Fastest sorting algorithm for a specific situation

Question

What is the fastest sorting algorithm for a large number (tens of thousands) of groups of 9 positive double precision values, where each group must be sorted individually? So it's got to sort fast a small number of possibly repeated double precision values, many times in a row. The values are in the [0..1] interval. I don't care about space complexity or stability, just about speed.

Answer 1

Sorting each group individually, merge sort would probably be easiest to implement with good results.

A sorting network would probably be the fastest solution: http://en.wikipedia.org/wiki/Sorting_network

Answer 2

Good question because this comes down to "Fastest way to sort an array of 9 elements", and most comparisons between and analysis of sorting methods are about large N. I assume the 'groups' are clearly defined and don't play a real role here.

You will probably have to benchmark a few candidates because a lot of factors (locality) come into play here.

In any case, making it parallel sounds like a good idea. Use Parallel.For() if you can use ,NET4.

Answer 3

I think you will need to try out a few examples to see what works best, as you have an unusual set of conditions. My guess that the best will be one of

• sorting network
• insertion sort
• quick sort (one level -- insertion sort below)
• merge sort

Given that double precision number are relatively long I suspect you will not do better with a radix sort, but feel free to add it in.

For what its worth, Java uses quick sort on doubles until the number of items to be sorted drops below 7, at which is uses insertion sort. The third option mimics that solution.

Also your overall problem is embarrassingly parallel so you want to make use of parallelism when possible. The problem looks too small for a distributed solution (more time would be lost in networking than saved), but if set up right, your problem can make use of multiple cores very effectively.

Answer 4

It looks like you want the most cycle-stingy way to sort 9 values. Since the number of values is limited, I would (as Kathy suggested) first do an unrolled insertion sort on the first 4 elements and the second 5 elements. Then I would merge those two groups.

Here's an unrolled insertion sort of 4 elements:

if (u[1] < u[0]) swap(u[0], u[1]);
if (u[2] < u[0]) swap(u[0], u[2]);
if (u[3] < u[0]) swap(u[0], u[3]);

if (u[2] < u[1]) swap(u[1], u[2]);
if (u[3] < u[1]) swap(u[1], u[3]);

if (u[3] < u[2]) swap(u[2], u[3]);

Here's a merge loop. The first set of 4 elements is in u, and the second set of 5 elements in in v. The result is in r.

i = j = k = 0;
while(i < 4 && j < 5){
  if (u[i] < v[j]) r[k++] = u[i++];
  else if (v[j] < u[i]) r[k++] = v[j++];
  else {
    r[k++] = u[i++];
    r[k++] = v[j++];
  }
}
while (i < 4) r[k++] = u[i++];
while (j < 5) r[k++] = v[j++];