Fast algorithm implementation to sort very small list

Question

This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small list 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

Solution 1

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 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.

Solution 2

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.

Solution 3

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.

Solution 4

Insertion sort is considered best for small arrays. See Fast stable sort for small arrays (under 32 or 64 elements)

Solution 5

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.

View more solutions

Comments

[kriss]

I asked basically the same question but with a more specific context (C implementation, arrays of 6 ints) and used cycle count register to evaluation performance. You can see results here : stackoverflow.com/questions/2786899/…

[Janus Troelsen]

related: Fastest sort of fixed length 6 int array

[Anycorn]

hello, I wrote some clarifications. I look more for implementation ideas

[Anycorn]

hi. I am interested more in implementation approach

[mathmike]

I'm not sure what you mean by "implementation approach". Are you looking for a discussion of assembly code?

[Anycorn]

not quite that low, but something that would show branches/instructions

[Anycorn]

the original program used some something like this, but performance was pretty low, my guess due to branch issues

[Guffa]

@aaa: I see... Well, to elliminate all branching you could do all the comparisons needed and combine the results into a key, and use that to get an index array from a precalculated dictionary of all possible results.

[Morwenn]

This algorithm is good but it is not optimal: it can perform up to 6 comparisons while an optimal algorithm shouldn't perform more than 5 comparisons.

[Emil Vikström]

I implemented insertion sort in C++ for embedded platforms. It turned out to be optimal in compiled binary size in all cases, probably because the optimizer was able to unravel the sort into sorting networks in those cases that was beneficial (when you have a list of known size at compile time).

[Eamon Nerbonne]

So, ancient answer here, but I misinterpreted the concept of an "optimal sorting network" when I first read this answer, so to clarify: an optimal sorting network does not actually use a minimal number of comparators! Sorting networks are restricted in that they always use the same fixed arrangement of comparators; i.e, that there's no branching in deciding which elements to compare. That's great for hardware implementations and GPGU, but it does mean you'll need more comparisons than strictly necessary, even at fairly small array sizes (I believe from 5 and up).

[M.J. Rayburn]

The site you provided for finding optimal sorting networks doesn't work for me, but I found this website users.telenet.be/bertdobbelaere/SorterHunter/…