Oblivious Sorts are Fun!

At the end of this page is a Javascript form which allows you to design and test your own oblivious sorting networks.

Oblivious sorts are also known as "network sorts" but I prefer the former name. It's more descriptive ... and more fun! Throughout this page, N will denote the number of items we wish to sort; we will call the items
    X1, X2, X3, ... XN.


N = 2

I'll start with simple examples (so simple that I won't need to explain "oblivious" until N=5). Oblivious sorts derive from one basic sorting machine or subroutine that I'll call "Cswap":
     Cswap(i, j): // define basic operation "Cswap"
           Assert i < j // (for convenience, the code substitutes Cswap(j, i), when i > j)
           If Xi > Xj // If the two elements are not in correct order ...
                 Then Swap Xi with Xj       // ... swap them
     End.  
Cswap is just a N=2 sorter so, once we have that machine as building block, the oblivious N=2 sort is trivial:
     Cswap(1, 2).  

When you input a Cswap below, just type the two positions separated with a hyphen. For Cswap(4,7) write "4-7".


N = 4 and N = 3

The N=4 sort is only slightly more interesting:
     Cswap(1, 2), Cswap(3, 4) // Sort two couples, like the first round of Final Four
     Cswap(1, 3), Cswap(2, 4) // Find Grand champion ... and Grand Loser
     Cswap(2, 3) // Complete the sort
Five calls to Cswap can distinguish among at most 25 = 32 initial orderings. Four calls couldn't possibly be enough for N=4, because 24 is only 16 but we need to distinguish among 4! = 24 initial orderings. Although N=4 requires a "comparator network" of only total size 5, the depth of the network is 3: even if the machines operated in parallel, the minimum delay would still be 3. But I won't worry about depth in this discussion. We'll just want to minimize total size.

We will use the N=4 sort as a building block. For example, the first ten comparators of our N=8 network will be
Sort4(1, 3, 5, 7)     // Sort the odd-numbered elements
Sort4(2, 4, 6, 8)     // Sort the even-numbered elements

The Sort4() can be built three different ways, depending on whether the initial comparison of X1 is with X2, X3, or X4. The effects, however are identical.

We can construct a 3-comparator N=3 sorter from the N=4 network by just deleting the two comparators involving element 4. Since log2 3! = 2.58 > 2, we know this 3-comparator network is minimal for N=3.

When you want to abbreviate a Sort4 (or Sort3) below, just type the four (or three) positions separated with hyphens. For Sort4(2,4,6,8) write "2-4-6-8".

It will often be convenient to save a comparator by putting only the largest and the smallest of four elements into proper position (to let subsequent comparators worry about the two middle elements).

To use such a Partial Sort4, prefix 'P', e.g. "P2-4-6-8".

BUT NOTE that now it MAY make a difference which of the three orderings is used. The Javascript below uses the ordering where X1 is initially compared with X2. (The reason it may make a difference is that prior steps may have imposed constraints on relationships that subsequent steps can exploit.)


N = 5

When N=5, things start to get more interesting. 5! = 120 < 27 = 128, so a solution with 7 comparators can not be immediately ruled out, but it would be a very tight squeeze. In fact there is no 7-comparator solution, oblivious or not, that will sort every possible input for N=5. Let's try for a 8-comparator sorter:

Start with Sort4(1, 2, 4, 5). This leaves everything but X3 sorted; X3 is still dangling in the middle. Can we position it with 3 more comparators?

It will seem that the answer is Yes. Compare X3 with the current X2. If a swap occurs, compare it also with X1 and we're done, with a total of 7 comparators. If the Cswap(2, 3) fails to swap, we need only compare X3 with X4 and X5 for a total of only eight comparators.

BUT that is against the rules! I've not yet explained why we call these "oblivious" sorts, but "oblivious" means "forgetful" and you are not allowed to remember whether a particular Cswap() succeeds or fails. Oblivious sorts are important in practical hardware engineering, but we need not worry about that -- just treat the concept as a source of puzzles!

In the N=5 sorter we are trying to build, a brute-force solution, once (1,2,4,5) are sorted, is to compare X3 with X1, X2, X4, X5 in order ... and such a trivial 9-comparator sorter is good enough for our purpose, since no oblivious sorter with fewer than 9 comparators exists for N=5.

I'll skip N=6 except to note that the minimal number of comparators is 12.


N = 8

Ken Batcher invented the concept of oblivious sorts about 1960, and came up with an elegant way to do an Oblivious sort when N is a power-of-two:
     Sort4(1, 3, 5, 7)  // sort the odd-numbered elements
     Sort4(2, 4, 6, 8)  // sort the even-numbered elements
     Cswap(1, 2); Cswap(3, 4); Cswap(5, 6); Cswap(7, 8);  // compare/swap like-ranked elements
     // After these 14 comparators, the sort is falling into place.
// Elements 1 and 8 are already in the correct position. The 2nd smallest element is in position 2 or 3, and so on.
// There are two elements that could cause trouble if we're not careful:
     Cswap(2, 5); Cswap(4, 7);  
     Cswap(2, 3); Cswap(4, 5); Cswap(6, 7);  // and a final zip-up finishes the sort!

This 19-comparator sort is optimal for N=8. To present this Batcher sort to the Javascript below, set N=8 and enter
    1-3-5-7 ; 2-4-6-8 ; 1-2 ; 3-4 ; 5-6 ; 7-8 ; 2-5 ; 4-7 ; 2-3 ; 4-5 ; 6-7


N = 7

By eliminating the three comparators involving X8 from the optimal N=8 sorter just given, you'll get an optimal sort for N=7 :
    1-3-5-7 ; 2-4-6 ; 1-2 ; 3-4 ; 5-6 ; 2-5 ; 4-7 ; 2-3 ; 4-5 ; 6-7

To confirm that this sorter for (N-1) must be valid if the corresponding N sorter is, simply pretend that there is a ghost element that fails all tests and ends in last place. There are several instances where, given a particularly good sorter for N. this trick leads directly to an optimal sorter for (N-1). Instead of deleting XN, you can delete X1 (imagine a ghost that passes all tests) but then you'll need to renumber all the points to use the Javascript below. (It may be possible to eliminate an interior point Xm, 1 < m < N, but it will be non-trivial: no longer is there an obvious way to imagine a "ghost.")

Eliminating a Cswap involving XN is trivial -- just erase it. Sort4 will change to Sort3; Sort3 will change to one Cswap. Psort4 will change to two Cswaps but take care about which two Cswaps: as noted above there may be subtle dependencies.


N = 9

I first learned of Oblivious sorting in the 1970's. (Gak! Time flies....) An article in a math journal mentioned Batcher sorting and I delighted myself by constructing a N=9 Oblivious sort using other principles. I'll publish it here, for the first time ever!
     Sort3(1, 2, 3), Sort3(4, 5, 6), Sort3(7, 8, 9) // Sort the rows of a 3-by-3 array.
     Sort3(1, 4, 7), Sort3(2, 5, 8), Sort3(3, 6, 9) // Sort the columns
     Cswap(2, 4), Cswap(3, 7), Cswap(6, 8) // Sort the diagonals
     Cswap(3, 4), Cswap(6, 7)  
     Cswap(4, 5), Cswap(5, 6) // Final cleanup

To present this optimal sort to the Javascript below, set N=9 and enter
    1-2-3 ; 4-5-6 ; 7-8-9 ; 1-4-7 ; 2-5-8 ; 3-6-9 ; 2-4 ; 3-7 ; 6-8 ; 3-4 ; 6-7 ; 4-5 ; 5-6

(The semi-colons will be ignored by the Javascript. I just use them to make this more readable for you.)

There are other ways to construct a N=9 oblivious sorter with only 25 comparators -- not surprising since the network above has lots of Sort3's, which are significantly less efficient than Sort4:

The above table also implies the best-known network. Best for N=13 was 46 until Hillis' work circa 1990. The results for N > 16 are major improvements made by Valsalam and Miikkulainen in 2011. (As seen, Sort4 is especially efficient. Sort_5 is very bad; its use as a building block will be avoided.)

N = 13

By now, you're wondering why I bothered to prepare this webpage. The Oblivious sorts of minimal size for very small N have been known for some time. The 60-comparator solution for N=16 was discovered in 1969; among cases N < 16, one N=13 was improved since then. Danny Hillis used this design problem to test his Predator-Prey Genetic Algorithm .. and in the 1990's his computer algorithm discovered a N=13 sorter with size 45. This seems exciting!

You're probably familiar with the genetic algorithm (GA), in which a population evolves under rules of mutation, genome crossover, and fitness selection, to improve its score for an objective. In the predator-prey variation of GA, the objective (catching prey) also changes under GA as prey's genomes evolve to avoid the evolving predators! In the case of Hillis' software to find good oblivious sorters, the prey are sets of test cases; their objective is the opposite of the predators. Good prey avoid the need for expensive prey (e.g., testing all 213 cases) and help jiggle the evolved predators out of local minima.

So, it was my excitement at seeing the solution discovered by Hillis' Predator-Prey method that led me to prepare this webpage. The "value added," if any, by me is in decomposing that sorter to make its inner working slightly more understandable. Unlike many optimal sorters, this one is not symmetric, high-vs-low.
(Step 1)  Psort(1, 4, 8, 11), Psort(2, 5, 9, 12), Psort(3, 6, 10, 13) // Organize all except Element 7
(Step 2)  Psort(7, 11, 12, 13) // Find the last-place; Give X7 an initial position
(Step 3)  Psort(1, 2, 3, 7) // Find the first-place; X7 now has actual rank of #4-#10
// X3 has actual rank of #2-#7; X11 has #5-#12
(Step 4)  Cswap(5, 10), Cswap(4, 10), Cswap(6, 9),
Cswap(8, 9), Cswap(5, 8), Cswap(4, 6)
// Work on the six middles from Step 1
// The best of them is now in 4 or 5, the worst in 9 or 10
  // But we know much more than that.
// Whichever of (4,5) is better has an actual rank of #2-#5
// Whichever of (4,5) is worse has an actual rank of #3-#7
// Whichever of (6,8) is better has an actual rank of #4-#8
// Whichever of (6,8) is worse has an actual rank of #6-#10
// Whichever of (9,10) is better has an actual rank of #6-#11
// Whichever of (9,10) is worse has an actual rank of #9-#12
(Step 5)  Sort4(9, 10, 11, 12) // After this, X1, X11, X12 and X13 are all in their exact final positions.
(Step 6)  Sort4(2, 3, 4, 5), Sort4(6, 7, 8, 9), Cswap(9, 10) // Makes much progress. Either 4 or 6 now belongs in the #4 slot, etc.
(Step 7)  Cswap(4, 6), Cswap(5, 7), Cswap(5, 6) // Done! Detailed non-exhaustive proof non-trivial properties of prior steps.

To present Hillis' N=13 sorter to the Javascript below, set N=13 and enter
P1-4-8-11 ; P2-5-9-12 ; P3-6-10-13
P7-11-12-13 ; P1-2-3-7
5-10 ; 4-10 ; 6-9 ; 8-9 ; 5-8 ; 4-6
9-10-11-12 ; 2-3-4-5 ; 6-7-8-9 ; 9-10
4-6 ; 5-7 ; 5-6

Are there special reasons why N=13 leads to this special peculiar-looking network? I think so. Recall that Sort4 and Psort4 are especially efficient. Because we have three groups of 4, integrating the 13th element leads to two more early opportunities to exploit Psort4. And the clever way that the middle six are arranged in Step4 immediately leads to three useful Sort4's. Especially note that the equivalences after Step4 (4 same as 5, 6 same as 8, 9 same as 10) means information is not wasted; any extra information would be "destroyed" by the subsequent Sort4's, so useless.

For a Sort4 to be very efficient, we want the four inputs to have equal status; otherwise information is wasted. The Psorts in Steps #1 and #2 are efficient by this measure, excpet for the forcing of X7. Step #4 manages to place six elements into three pairs very nicely. Elements 11 and 12 presented to Sort4 in Step #5 could belong as low as slot 5, compared with 6 for elements 9 and 10, but all four elements could be as low as slot 12, but no lower. The elements 2-3-4-5 for Step #6 all have identical max/min status. Elements 6-7-8-9 are almost identical: three have max/min of 4/10, but element 9 has 5/9.

It seems slightly sad that this pattern was discovered by computer; a human would have gotten great pleasure from its discovery!


N = 12

Here's an optimal N=12 sorter related to the N=13 solution.
P1-4-7-10 ; P2-5-8-11 ; P3-6-9-12
10-11 ; 11-12 ; 5-9 ; 4-9 ; 6-8 ; 7-8 ; 5-7 ; 4-6
8-9-10-11 ; 1-2 ; 1-3
2-3-4-5 ; 5-6-7-8
4-5 ; 8-9


N = 16

In 1969, a N=16 sorter smaller than Batcher's was discovered. To present this best-known N=16 sorter to the Javascript below, set N=16 and enter
P1-2-3-4 ; P5-6-7-8 ; P9-10-11-12 ; P13-14-15-16
P1-5-9-13 ; P2-6-10-14 ; P3-7-11-15 ; P4-8-12-16
6-11 ; 7-10 ; 4-13 ; 14-15 ; 8-12 ; 2-3 ; 5-9
2-5 ; 8-14 ; 3-9 ; 12-15 ; 6-7 ; 10-11
3-5 ; 12-14 ; 4-9 ; 8-13
7-9 ; 11-13 ; 4-6 ; 8-10
4-5 ; 6-7 ; 8-9 ; 10-11 ; 12-13
7-8 ; 9-10


N = 15 or N = 14

Start with the 60-comparator network for N=16; eliminate the four comparators involving X16 and get a 56-comparator network for N=15, the best known. From there, eliminate the five comparators involving X15 and get a 51-comparator network for N=14, again the best known.


N = 14? or N=17? etc.

But is the best-known N=14 network really the best? Hillis found his N=13 sorter in the 1990's I think, when computers were much slower. Perhaps you can improve on the best known sorters! (The Javascript below will probably be useless in pursuing such a thing.) The N=17 case might be relatively easy pickings since, as far as I know, little effort has been spent on it. (Probably not real easy pickings however; I've spent hours looking for good networks, with only frustration.) And what about N=14? Is there an elegant 50-comparator solution? Looking a tthe list of "efficiencies" above, you'll see that a 50-comparator N=14 network would be more "efficient" than Hillis' N=13 network. I'll bet none exists.

If you've read this far, and found anything interesting, please send me e-mail using the address at the end of this page.


Testing a sort with a Javascript

There are N! possible initial orderings. For N=14, that would be 87 billion. HOWEVER, it is a neat theorem that you needn't test all of them; indeed you can assume that 0 and 1 are the only X values. That leaves just 214 = 16,384 possibilities; a much more practical number. The Javascript will generate all 2N test cases, and depict their progress. Even several thousand cases would produce a tediously long display, so for brevity I'll suppress the cases that have become sorted, or have been reduced to another case. Running N=16, there will be a delay of a few seconds during startup, as the thousands of cases are prepared for printing. (You can edit the Javascript and allow even bigger N if you wish, but your browser will probably give you busy warnings!)

Sorting a strong of 0's and 1's means moving all the 1's to the right. You can watch the number of unsorted cases diminish as the sort progresses, and disappear entirely by the end, if the network functions perfectly.

The following form allows you to input and test your own oblivious sort network. Enter the comparators in the form "K-J" for Cswap(k, j) using spaces, newlines, commas or semicolons to separate comparators. (The default is Hillis' N=13 network.)

Set the value of N; type comparators into the input box; then press "Show results."
Select Array size N Set time delay in seconds
 
  3    4    5     6    7    8    9     10    11    12     13    14     15    16   
Enter comparators:Run simulationClear input


 

 


My e-mail address: