Some important sorting networks (e.g. Batcher's bitonic and odd-even networks) are based on a mergesort-like algorithm:
- Merge each element into sorted pairs: merge(0, 1), merge(2, 3), merge(4, 5), ...
- Merge each pair of 2-tuples into sorted 4-tuples: merge(0:1, 2:3), merge(4:5, 6:7), merge(8:9, 10:11), ...
- Merge each pair of 4-tuples into sorted 8-tuples: merge(0:3, 4:7), merge(8:11, 12:15), merge(16:19, 20:23), ...
- ...
- Merge the final two halves: merge(0:n/2-1, n/2:n-1)
This also applies to the idea for "Sorting Medium-Sized Arrays With Sorting Networks" in this paper.
By visualizing the network as a mergesort, it is possible to check that the network is correct in polynomial time, rather than the currently-implemented exponential time algorithm.
This is discussed by Knuth (TAOCP v3, second edition, Section 5.3.4, p. 224) while proving that Batcher's odd-even merge network is correct. Essentially, to check than an (n,n)-merging network is correct, you employ the 0-1 principle on all possible inputs, which are much more restricted in the case of a merging network since each half of the input must itself be sorted:
- 0 zeros, n ones
- 1 zero, n - 1 ones
- ...
- n zeros, 0 ones
So you just need to check the cartesian product of these n + 1 inputs with itself, for a total of (n + 1)^2 checks that the merging network is correct.
Thus, the cost of checking each merging pass is O(n^2) applications of a merging network (a slice of the full sorting network). Since a mergesort algorithm has log n passes, the total cost is O(n^2 log n) applications. Well known merging networks such as the aforementioned ones by Batcher have O(n log n) comparators, so if this analysis is correct, this would be a O(n^3 log^2 n) algorithm -- and even if there is a mistake somewhere, it is definitely polynomial.
I guess the only remaining issue is that the checking algorithm needs to identify the different layers of mergesort. My proposal is to change the input format so that mergesort levels are separated by a blank line. So, for instance, Batcher's odd-even sorting network for n = 16 from #15 could be represented as:
0:1,2:3,4:5,6:7,8:9,10:11,12:13,14:15
0:2,1:3,4:6,5:7,8:10,9:11,12:14,13:15
1:2,5:6,9:10,13:14
0:4,1:5,2:6,3:7,8:12,9:13,10:14,11:15
2:4,3:5,10:12,11:13
1:2,3:4,5:6,9:10,11:12,13:14
0:8,1:9,2:10,3:11,4:12,5:13,6:14,7:15
4:8,5:9,6:10,7:11
2:4,3:5,6:8,7:9,10:12,11:13
1:2,3:4,5:6,7:8,9:10,11:12,13:14
The script could support a different command for checking such network, e.g. check-mergesort in addition to the existing check.
Lastly, it is pretty easy to filter which comparators belong to which pair of k-tuples being checked.
Let me know what you think about this idea. If you're interested but do not have the bandwidth to implement it, I may consider coming back to it after I clear some of my own backlog in a couple of months.
Some important sorting networks (e.g. Batcher's bitonic and odd-even networks) are based on a mergesort-like algorithm:
This also applies to the idea for "Sorting Medium-Sized Arrays With Sorting Networks" in this paper.
By visualizing the network as a mergesort, it is possible to check that the network is correct in polynomial time, rather than the currently-implemented exponential time algorithm.
This is discussed by Knuth (TAOCP v3, second edition, Section 5.3.4, p. 224) while proving that Batcher's odd-even merge network is correct. Essentially, to check than an (n,n)-merging network is correct, you employ the 0-1 principle on all possible inputs, which are much more restricted in the case of a merging network since each half of the input must itself be sorted:
So you just need to check the cartesian product of these n + 1 inputs with itself, for a total of (n + 1)^2 checks that the merging network is correct.
Thus, the cost of checking each merging pass is O(n^2) applications of a merging network (a slice of the full sorting network). Since a mergesort algorithm has log n passes, the total cost is O(n^2 log n) applications. Well known merging networks such as the aforementioned ones by Batcher have O(n log n) comparators, so if this analysis is correct, this would be a O(n^3 log^2 n) algorithm -- and even if there is a mistake somewhere, it is definitely polynomial.
I guess the only remaining issue is that the checking algorithm needs to identify the different layers of mergesort. My proposal is to change the input format so that mergesort levels are separated by a blank line. So, for instance, Batcher's odd-even sorting network for n = 16 from #15 could be represented as:
The script could support a different command for checking such network, e.g.
check-mergesortin addition to the existingcheck.Lastly, it is pretty easy to filter which comparators belong to which pair of k-tuples being checked.
Let me know what you think about this idea. If you're interested but do not have the bandwidth to implement it, I may consider coming back to it after I clear some of my own backlog in a couple of months.