fast algorithm implementation to sort very small set

Question

hello.

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small set of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the best approach/algorithm?

my approach was to use the max/min functions (10 functions to sort 4 numbers, no branches, iirc).

// s(i,j) == max(i,j), min(i,j)
i,j = s(i,j)
k,l = s(k,l)
i,k = s(i,k) // i on top
j,l = s(j,l) // l on bottom
j,k = s(j,k)

I guess my question pertains more to implementation, rather than type of algorithm.

At this point it becomes somewhat hardware dependent , so let us assume Intel 64-bit processor with SSE3 .

Thanks

Answer 1

For such a small data set, you want as simple of algorithm as possible. More likely than not, a basic Insertion Sort will do as well as you could want.

Would need to know more about the system this is running on, how many times you need to do this sort a second, etc... but the general rule in small sorts is to keep it simple. Quicksort and the like are not beneficial.

Answer 2

Insertion sort is considered best for small arrays. See http://stackoverflow.com/questions/1276716/fast-stable-sort-for-small-arrays-under-32-or-64-elements

Answer 3

I see you already have a solution that uses 5 comparisons (assuming that s(i,j) compares the two numbers once, and either swaps them or not). If you stick to comparison-based sorting, then you can't do it with any fewer than 5 comparisons.

This can be proven because there are 4! = 24 possible ways to order 4 numbers. Each comparison can only cut the possibilities in half, so with 4 comparisons you could only distinguish between 2^4 = 16 possible orderings.

Answer 4

For small arrays like this, you should probably look into sorting networks. As you can see on that page, insertion sort can be expressed as a sorting network. However, if you know the size of the array beforehand, you can devise an optimal network. Take a look at this site that can do help you to find optimal sorting networks for a given size of array (though optimal is only guaranteed up to a size of 16 I believe). The comparators are even grouped together in operations that can be done in parallel. The comparators are essentially the same as your s(x,y) function though if you really want this to be fast, you shouldn't be using min and max because then you're doing twice the number of comparisons that are necessary.

If you need this sorting algorithm to work on a wide range of sizes, then you should probably just go with insertion sort as others have suggested.

Answer 5

To sort small amounts of numbers you want a simple algorithm as complexity adds more overhead.

The most efficient way to sort for example four items would be to unravel the sorting algorithm to linear comparisons, thus elliminating all overhead:

function sort(i,j,k,l) {
  if (i < j) {
    if (j < k) {
      if (k < l) return [i,j,k,l];
      if (j < l) return [i,j,l,k];
      if (i < l) return [i,l,j,k];
      return [l,i,j,k];
    } else if (i < k) {
      if (j < l) return [i,k,j,l];
      if (k < l) return [i,k,l,j];
      if (i < l) return [i,l,k,j];
      return [l,i,k,j];
    } else {
      if (j < l) return [k,i,j,l];
      if (i < l) return [k,i,l,j];
      if (k < l) return [k,l,i,j];
      return [l,k,i,j];
    }
  } else {
    if (i < k) {
      if (k < l) return [j,i,k,l];
      if (i < l) return [j,i,l,k];
      if (j < l) return [j,l,i,k];
      return [l,j,i,k];
    } else if (j < k) {
      if (i < l) return [j,k,i,l];
      if (k < l) return [j,k,l,i];
      if (j < l) return [j,l,k,i];
      return [l,j,k,i];
    } else {
      if (i < l) return [k,j,i,l];
      if (j < l) return [k,j,l,i];
      if (k < l) return [k,l,j,i];
      return [l,k,j,i];
    }
  }
}

However, the code grows a lot for each extra item you add. Adding a fifth item makes the code roughly four times larger. At eight items it would be roughly 30000 lines, so although it's still the most efficient, it's a lot of code, and you would have to write a program that writes the code to get it correct.

Answer 6

Sorting networks can be easily implemented in SIMD, although it starts to get ugly at around N = 16. For N = 4 or N = 8 though this would be a good choice. Ideally you need lots of small data sets to sort concurrently, i.e. if you are sorting 8 bit values then you want at least 16 data sets to sort - it's much harder to do this kind of thing across SIMD vectors.

See also: http://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array