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.
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|
When you input a Cswap below, just type the two positions separated with a hyphen. For Cswap(4,7) write "4-7".
|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|
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".
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.
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.
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
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
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.
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|
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
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:
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(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.|
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!
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
In 1969, a N=16 sorter smaller than Batcher's was discovered.
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
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.
If you've read this far, and found anything interesting, please send me e-mail using the address at the end of this page.
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.)