Fast algorithm implementation to sort very small list

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.

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.

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.