Sorting Networks - which networks allow skipping a comparison?

Question

GCC's implementation of qsort uses the median-of-3 to choose a pivot. While at it, the 3 elements are sorted with a sorting network.

A sorting network for 3 elements would normally require 3 comparisons. But in this particular implementation, the last comparison can be skipped, depending on the comparison before:

if(a[0] > a[1]) swap(a[0], a[1]);
if(a[1] > a[2]) swap(a[1], a[2]);
else goto jump;
if(a[0] > a[1]) swap(a[0], a[1]);
jump:;

Could something similar be done for networks with n = 4...16 (the ones that have a known minimum optimal number of comparisons)? If so, which ones and what would they look like?

UPDATE: So far, I have found one other network, that allows skipping one comparison:

// sorting network for 5 elements
if (a[0] > a[1]) { SWAP(a[0], a[1]); }
if (a[2] > a[3]) { SWAP(a[2], a[3]); }

if (a[1] > a[3]) { SWAP(a[1], a[3]); }
if (a[2] > a[4]) { SWAP(a[2], a[4]); }

if (a[0] > a[2]) { SWAP(a[0], a[2]); }
if (a[1] > a[4]) { SWAP(a[1], a[4]); }

if (a[1] > a[2]) { SWAP(a[1], a[2]); }
if (a[3] > a[4]) { SWAP(a[3], a[4]); }
else { goto jump; }

if (a[2] > a[3]) { SWAP(a[2], a[3]); }
jump:;

I tested this with all permutations of 12345, and it sorts all of them correctly.

It seems by the time you get to the conditional compare, if no swap occurs, then that final comparison would be redundant. You could probably keep track of which elements have already been compared by using a second array of original indices and swapping that array along with the data, and an array of size (n^2 - n) / 2 for the number of possible comparisons of elements (n things taken 2 at a time), initialized to zeros and set to one for each compare. — rcgldr, Oct 07 '16 at 00:16

score 0 · Answer 1 · edited May 23 '17 at 11:45

Leaving aside optimal sorting networks, the following image shows a way to create a sorting network of any size n+1 by using a sorting network of size n then performing n additional comparisons to put the last element in place (this is typically how insertion sort works once translated to a sorting network):

The image makes it pretty obvious than if the element n+1 is already the greatest one, then you can skip every comparator after the one that compared the elements n and n+1. Basically, once any the the n last comparators returns false, you skip the following ones. In the grand scheme of things, I'd say that it would be possible to skip comparisons in most sorting networks.

That said, once you have such conditionals in your sorting algorithm, then it isn't a sorting network anymore, and you lose the benefits of sorting networks: no branch prediction problem occurs when properly implemented.

If your goal is just to sort a small collection with as few comparisons and swaps as possible, then you can unroll every possible path of a sorting algorithm and then perform an optimal number of moves/swaps for every path, but such a method becomes outright unmaintainable above 4 elements, and it's unlikely your types have move and comparison operations expensive enough to justify such an algorithm.

Sorting Networks - which networks allow skipping a comparison?

1 Answers1