Batcher Odd-Even Mergesort Sorting Network

# Batcher Odd-Even Mergesort Sorting Network Generator
# https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
# https://en.wikipedia.org/wiki/Sorting_network
gen = lambda N: [
    [
        (i+j, i+j+(1<<k))
        for j in range((1<<k)%(1<<p), N-(1<<k), 2<<k)
        for i in range(min(1<<k, N-j-(1<<k)))
        if (((i+j)^(i+j+(1<<k)))>>(p+1)) == 0
    ]
    for p in range((N-1).bit_length())
    for k in range(p,-1,-1)
]

for N in [2, 4, 8, 16, 32, 64]:
    net = gen(N)
    print("```mermaid")
    print("---")
    print("title: Batcher Odd-Even Mergesort Sorting Network N={}, size={}, depth={}".format(N, sum(map(len, net)), len(net)))
    print("---")
    print("sequenceDiagram")
    print("par")
    for i, w in enumerate(net):
        print("and tick {}".format(i+1))
        for a, b in w:
            print("{}-){}: ".format(a, b))
    print("end")
    print("```")
    print()

---
title: Batcher Odd-Even Mergesort Sorting Network N=2, size=1, depth=1
---
sequenceDiagram
par
and tick 1
0-)1: 
end

---
title: Batcher Odd-Even Mergesort Sorting Network N=4, size=5, depth=3
---
sequenceDiagram
par
and tick 1
0-)1: 
2-)3: 
and tick 2
0-)2: 
1-)3: 
and tick 3
1-)2: 
end

---
title: Batcher Odd-Even Mergesort Sorting Network N=8, size=19, depth=6
---
sequenceDiagram
par
and tick 1
0-)1: 
2-)3: 
4-)5: 
6-)7: 
and tick 2
0-)2: 
1-)3: 
4-)6: 
5-)7: 
and tick 3
1-)2: 
5-)6: 
and tick 4
0-)4: 
1-)5: 
2-)6: 
3-)7: 
and tick 5
2-)4: 
3-)5: 
and tick 6
1-)2: 
3-)4: 
5-)6: 
end

---
title: Batcher Odd-Even Mergesort Sorting Network N=16, size=63, depth=10
---
sequenceDiagram
par
and tick 1
0-)1: 
2-)3: 
4-)5: 
6-)7: 
8-)9: 
10-)11: 
12-)13: 
14-)15: 
and tick 2
0-)2: 
1-)3: 
4-)6: 
5-)7: 
8-)10: 
9-)11: 
12-)14: 
13-)15: 
and tick 3
1-)2: 
5-)6: 
9-)10: 
13-)14: 
and tick 4
0-)4: 
1-)5: 
2-)6: 
3-)7: 
8-)12: 
9-)13: 
10-)14: 
11-)15: 
and tick 5
2-)4: 
3-)5: 
10-)12: 
11-)13: 
and tick 6
1-)2: 
3-)4: 
5-)6: 
9-)10: 
11-)12: 
13-)14: 
and tick 7
0-)8: 
1-)9: 
2-)10: 
3-)11: 
4-)12: 
5-)13: 
6-)14: 
7-)15: 
and tick 8
4-)8: 
5-)9: 
6-)10: 
7-)11: 
and tick 9
2-)4: 
3-)5: 
6-)8: 
7-)9: 
10-)12: 
11-)13: 
and tick 10
1-)2: 
3-)4: 
5-)6: 
7-)8: 
9-)10: 
11-)12: 
13-)14: 
end

---
title: Batcher Odd-Even Mergesort Sorting Network N=32, size=191, depth=15
---
sequenceDiagram
par
and tick 1
0-)1: 
2-)3: 
4-)5: 
6-)7: 
8-)9: 
10-)11: 
12-)13: 
14-)15: 
16-)17: 
18-)19: 
20-)21: 
22-)23: 
24-)25: 
26-)27: 
28-)29: 
30-)31: 
and tick 2
0-)2: 
1-)3: 
4-)6: 
5-)7: 
8-)10: 
9-)11: 
12-)14: 
13-)15: 
16-)18: 
17-)19: 
20-)22: 
21-)23: 
24-)26: 
25-)27: 
28-)30: 
29-)31: 
and tick 3
1-)2: 
5-)6: 
9-)10: 
13-)14: 
17-)18: 
21-)22: 
25-)26: 
29-)30: 
and tick 4
0-)4: 
1-)5: 
2-)6: 
3-)7: 
8-)12: 
9-)13: 
10-)14: 
11-)15: 
16-)20: 
17-)21: 
18-)22: 
19-)23: 
24-)28: 
25-)29: 
26-)30: 
27-)31: 
and tick 5
2-)4: 
3-)5: 
10-)12: 
11-)13: 
18-)20: 
19-)21: 
26-)28: 
27-)29: 
and tick 6
1-)2: 
3-)4: 
5-)6: 
9-)10: 
11-)12: 
13-)14: 
17-)18: 
19-)20: 
21-)22: 
25-)26: 
27-)28: 
29-)30: 
and tick 7
0-)8: 
1-)9: 
2-)10: 
3-)11: 
4-)12: 
5-)13: 
6-)14: 
7-)15: 
16-)24: 
17-)25: 
18-)26: 
19-)27: 
20-)28: 
21-)29: 
22-)30: 
23-)31: 
and tick 8
4-)8: 
5-)9: 
6-)10: 
7-)11: 
20-)24: 
21-)25: 
22-)26: 
23-)27: 
and tick 9
2-)4: 
3-)5: 
6-)8: 
7-)9: 
10-)12: 
11-)13: 
18-)20: 
19-)21: 
22-)24: 
23-)25: 
26-)28: 
27-)29: 
and tick 10
1-)2: 
3-)4: 
5-)6: 
7-)8: 
9-)10: 
11-)12: 
13-)14: 
17-)18: 
19-)20: 
21-)22: 
23-)24: 
25-)26: 
27-)28: 
29-)30: 
and tick 11
0-)16: 
1-)17: 
2-)18: 
3-)19: 
4-)20: 
5-)21: 
6-)22: 
7-)23: 
8-)24: 
9-)25: 
10-)26: 
11-)27: 
12-)28: 
13-)29: 
14-)30: 
15-)31: 
and tick 12
8-)16: 
9-)17: 
10-)18: 
11-)19: 
12-)20: 
13-)21: 
14-)22: 
15-)23: 
and tick 13
4-)8: 
5-)9: 
6-)10: 
7-)11: 
12-)16: 
13-)17: 
14-)18: 
15-)19: 
20-)24: 
21-)25: 
22-)26: 
23-)27: 
and tick 14
2-)4: 
3-)5: 
6-)8: 
7-)9: 
10-)12: 
11-)13: 
14-)16: 
15-)17: 
18-)20: 
19-)21: 
22-)24: 
23-)25: 
26-)28: 
27-)29: 
and tick 15
1-)2: 
3-)4: 
5-)6: 
7-)8: 
9-)10: 
11-)12: 
13-)14: 
15-)16: 
17-)18: 
19-)20: 
21-)22: 
23-)24: 
25-)26: 
27-)28: 
29-)30: 
end

---
title: Batcher Odd-Even Mergesort Sorting Network N=64, size=543, depth=21
---
sequenceDiagram
par
and tick 1
0-)1: 
2-)3: 
4-)5: 
6-)7: 
8-)9: 
10-)11: 
12-)13: 
14-)15: 
16-)17: 
18-)19: 
20-)21: 
22-)23: 
24-)25: 
26-)27: 
28-)29: 
30-)31: 
32-)33: 
34-)35: 
36-)37: 
38-)39: 
40-)41: 
42-)43: 
44-)45: 
46-)47: 
48-)49: 
50-)51: 
52-)53: 
54-)55: 
56-)57: 
58-)59: 
60-)61: 
62-)63: 
and tick 2
0-)2: 
1-)3: 
4-)6: 
5-)7: 
8-)10: 
9-)11: 
12-)14: 
13-)15: 
16-)18: 
17-)19: 
20-)22: 
21-)23: 
24-)26: 
25-)27: 
28-)30: 
29-)31: 
32-)34: 
33-)35: 
36-)38: 
37-)39: 
40-)42: 
41-)43: 
44-)46: 
45-)47: 
48-)50: 
49-)51: 
52-)54: 
53-)55: 
56-)58: 
57-)59: 
60-)62: 
61-)63: 
and tick 3
1-)2: 
5-)6: 
9-)10: 
13-)14: 
17-)18: 
21-)22: 
25-)26: 
29-)30: 
33-)34: 
37-)38: 
41-)42: 
45-)46: 
49-)50: 
53-)54: 
57-)58: 
61-)62: 
and tick 4
0-)4: 
1-)5: 
2-)6: 
3-)7: 
8-)12: 
9-)13: 
10-)14: 
11-)15: 
16-)20: 
17-)21: 
18-)22: 
19-)23: 
24-)28: 
25-)29: 
26-)30: 
27-)31: 
32-)36: 
33-)37: 
34-)38: 
35-)39: 
40-)44: 
41-)45: 
42-)46: 
43-)47: 
48-)52: 
49-)53: 
50-)54: 
51-)55: 
56-)60: 
57-)61: 
58-)62: 
59-)63: 
and tick 5
2-)4: 
3-)5: 
10-)12: 
11-)13: 
18-)20: 
19-)21: 
26-)28: 
27-)29: 
34-)36: 
35-)37: 
42-)44: 
43-)45: 
50-)52: 
51-)53: 
58-)60: 
59-)61: 
and tick 6
1-)2: 
3-)4: 
5-)6: 
9-)10: 
11-)12: 
13-)14: 
17-)18: 
19-)20: 
21-)22: 
25-)26: 
27-)28: 
29-)30: 
33-)34: 
35-)36: 
37-)38: 
41-)42: 
43-)44: 
45-)46: 
49-)50: 
51-)52: 
53-)54: 
57-)58: 
59-)60: 
61-)62: 
and tick 7
0-)8: 
1-)9: 
2-)10: 
3-)11: 
4-)12: 
5-)13: 
6-)14: 
7-)15: 
16-)24: 
17-)25: 
18-)26: 
19-)27: 
20-)28: 
21-)29: 
22-)30: 
23-)31: 
32-)40: 
33-)41: 
34-)42: 
35-)43: 
36-)44: 
37-)45: 
38-)46: 
39-)47: 
48-)56: 
49-)57: 
50-)58: 
51-)59: 
52-)60: 
53-)61: 
54-)62: 
55-)63: 
and tick 8
4-)8: 
5-)9: 
6-)10: 
7-)11: 
20-)24: 
21-)25: 
22-)26: 
23-)27: 
36-)40: 
37-)41: 
38-)42: 
39-)43: 
52-)56: 
53-)57: 
54-)58: 
55-)59: 
and tick 9
2-)4: 
3-)5: 
6-)8: 
7-)9: 
10-)12: 
11-)13: 
18-)20: 
19-)21: 
22-)24: 
23-)25: 
26-)28: 
27-)29: 
34-)36: 
35-)37: 
38-)40: 
39-)41: 
42-)44: 
43-)45: 
50-)52: 
51-)53: 
54-)56: 
55-)57: 
58-)60: 
59-)61: 
and tick 10
1-)2: 
3-)4: 
5-)6: 
7-)8: 
9-)10: 
11-)12: 
13-)14: 
17-)18: 
19-)20: 
21-)22: 
23-)24: 
25-)26: 
27-)28: 
29-)30: 
33-)34: 
35-)36: 
37-)38: 
39-)40: 
41-)42: 
43-)44: 
45-)46: 
49-)50: 
51-)52: 
53-)54: 
55-)56: 
57-)58: 
59-)60: 
61-)62: 
and tick 11
0-)16: 
1-)17: 
2-)18: 
3-)19: 
4-)20: 
5-)21: 
6-)22: 
7-)23: 
8-)24: 
9-)25: 
10-)26: 
11-)27: 
12-)28: 
13-)29: 
14-)30: 
15-)31: 
32-)48: 
33-)49: 
34-)50: 
35-)51: 
36-)52: 
37-)53: 
38-)54: 
39-)55: 
40-)56: 
41-)57: 
42-)58: 
43-)59: 
44-)60: 
45-)61: 
46-)62: 
47-)63: 
and tick 12
8-)16: 
9-)17: 
10-)18: 
11-)19: 
12-)20: 
13-)21: 
14-)22: 
15-)23: 
40-)48: 
41-)49: 
42-)50: 
43-)51: 
44-)52: 
45-)53: 
46-)54: 
47-)55: 
and tick 13
4-)8: 
5-)9: 
6-)10: 
7-)11: 
12-)16: 
13-)17: 
14-)18: 
15-)19: 
20-)24: 
21-)25: 
22-)26: 
23-)27: 
36-)40: 
37-)41: 
38-)42: 
39-)43: 
44-)48: 
45-)49: 
46-)50: 
47-)51: 
52-)56: 
53-)57: 
54-)58: 
55-)59: 
and tick 14
2-)4: 
3-)5: 
6-)8: 
7-)9: 
10-)12: 
11-)13: 
14-)16: 
15-)17: 
18-)20: 
19-)21: 
22-)24: 
23-)25: 
26-)28: 
27-)29: 
34-)36: 
35-)37: 
38-)40: 
39-)41: 
42-)44: 
43-)45: 
46-)48: 
47-)49: 
50-)52: 
51-)53: 
54-)56: 
55-)57: 
58-)60: 
59-)61: 
and tick 15
1-)2: 
3-)4: 
5-)6: 
7-)8: 
9-)10: 
11-)12: 
13-)14: 
15-)16: 
17-)18: 
19-)20: 
21-)22: 
23-)24: 
25-)26: 
27-)28: 
29-)30: 
33-)34: 
35-)36: 
37-)38: 
39-)40: 
41-)42: 
43-)44: 
45-)46: 
47-)48: 
49-)50: 
51-)52: 
53-)54: 
55-)56: 
57-)58: 
59-)60: 
61-)62: 
and tick 16
0-)32: 
1-)33: 
2-)34: 
3-)35: 
4-)36: 
5-)37: 
6-)38: 
7-)39: 
8-)40: 
9-)41: 
10-)42: 
11-)43: 
12-)44: 
13-)45: 
14-)46: 
15-)47: 
16-)48: 
17-)49: 
18-)50: 
19-)51: 
20-)52: 
21-)53: 
22-)54: 
23-)55: 
24-)56: 
25-)57: 
26-)58: 
27-)59: 
28-)60: 
29-)61: 
30-)62: 
31-)63: 
and tick 17
16-)32: 
17-)33: 
18-)34: 
19-)35: 
20-)36: 
21-)37: 
22-)38: 
23-)39: 
24-)40: 
25-)41: 
26-)42: 
27-)43: 
28-)44: 
29-)45: 
30-)46: 
31-)47: 
and tick 18
8-)16: 
9-)17: 
10-)18: 
11-)19: 
12-)20: 
13-)21: 
14-)22: 
15-)23: 
24-)32: 
25-)33: 
26-)34: 
27-)35: 
28-)36: 
29-)37: 
30-)38: 
31-)39: 
40-)48: 
41-)49: 
42-)50: 
43-)51: 
44-)52: 
45-)53: 
46-)54: 
47-)55: 
and tick 19
4-)8: 
5-)9: 
6-)10: 
7-)11: 
12-)16: 
13-)17: 
14-)18: 
15-)19: 
20-)24: 
21-)25: 
22-)26: 
23-)27: 
28-)32: 
29-)33: 
30-)34: 
31-)35: 
36-)40: 
37-)41: 
38-)42: 
39-)43: 
44-)48: 
45-)49: 
46-)50: 
47-)51: 
52-)56: 
53-)57: 
54-)58: 
55-)59: 
and tick 20
2-)4: 
3-)5: 
6-)8: 
7-)9: 
10-)12: 
11-)13: 
14-)16: 
15-)17: 
18-)20: 
19-)21: 
22-)24: 
23-)25: 
26-)28: 
27-)29: 
30-)32: 
31-)33: 
34-)36: 
35-)37: 
38-)40: 
39-)41: 
42-)44: 
43-)45: 
46-)48: 
47-)49: 
50-)52: 
51-)53: 
54-)56: 
55-)57: 
58-)60: 
59-)61: 
and tick 21
1-)2: 
3-)4: 
5-)6: 
7-)8: 
9-)10: 
11-)12: 
13-)14: 
15-)16: 
17-)18: 
19-)20: 
21-)22: 
23-)24: 
25-)26: 
27-)28: 
29-)30: 
31-)32: 
33-)34: 
35-)36: 
37-)38: 
39-)40: 
41-)42: 
43-)44: 
45-)46: 
47-)48: 
49-)50: 
51-)52: 
53-)54: 
55-)56: 
57-)58: 
59-)60: 
61-)62: 
end

mizar/sorting_network.md