Optimal Batcher ungerade-gerade fusionieren Netzwerke für andere Größen als 2 ^ n

Heute habe ich versucht, Sortier-Netzwerke bis zur Größe 32 mit einer minimalen Anzahl von Vergleichs-Austausch-Einheiten zu implementieren (optimal in size , nicht in depth ) . Ab sofort konnte ich die folgenden Ressourcen verwenden, um meine Netzwerke zu generieren:

• Sortieren von Netzwerken 0 bis 16: Perls Algorithm::Networksort -Modul mit "Best" -Algorithmus. Leider bietet es nur die bekanntesten Netzwerke bis Größe 16.

• Sortieren von Netzwerken von 17 bis 23: Verwenden von Symmetrie und evolutionärer Suche zum Minimieren von Sortiernetzwerken von Valsalam und Miikkulainen.

Das Papier Suche nach besseren Sortier-Netzwerken von Baddar gibt die minimale Anzahl von Vergleichsaustauscheinheiten an, von denen bekannt ist, dass sie zum Sortieren von Netzwerken 0 bis 32 benötigt werden (nicht aktuell, da Valsalam und Miikkulainen bessere Algorithmen für die Größen 17, 18, 19, 20, 21 und 22 bereitstellen) Die Methode, die verwendet wird, um sie zu finden: Im Grunde muss man das Array aufteilen, um zwei zu sortieren, und dann beide Hälften mit den bekanntesten Sortier-Netzwerken für diese Größen sortieren, bevor sie mit einem ungeraden-geraden Merge-Netzwerk zusammengeführt werden (was dem Merge-Schritt entspricht) von Batchers ungerade-gerade mergesort ).

Die Wikipedia-Seite gibt die folgende Python-Implementierung für Batters ungeraden-geraden Mergesort:

Der Schritt oddeven_merge ist bereits isoliert, daher war es einfach, ihn alleine zu verwenden, um die Indexpaare zu generieren, die zum Zusammenführen der beiden sortierten Hälften des ursprünglichen Arrays benötigt werden. Diese Implementierung funktioniert jedoch nur, wenn die Größe des Arrays eine Potenz von 2 ist. Daher konnte ich nur die minimale bekannte Anzahl von Vergleichsaustauscheinheiten finden, die für ein Sortiernetzwerk der Größe 32 benötigt wird. Entfernen der Indexpaare mit dem Der höchste Index erlaubte es mir, das entsprechende Sortiernetzwerk der Größe 31 zu finden, aber das Entfernen von mehr Paaren brachte nicht die besten bekannten Ergebnisse für Größen kleiner als 31.

Perls Algorithm::Networksort -Modul bietet eine alternative Mergesort-Implementierung für ungerade und gerade Batcher, die mit Arrays jeder Größe funktioniert, nicht nur mit Potenzen von 2. Daher habe ich beschlossen, einen Blick darauf zu werfen, um herauszufinden, ob ich den Merging-Schritt extrahieren könnte aus dem Algorithmus. Hier ist das Python-Äquivalent (es entspricht auch dem von Knuth in Die Kunst des Computerprogrammierens Vol. 3 beschriebenen Algorithmus):

Leider scheint dieser Algorithmus ein wenig kryptisch für meine Augen zu sein, und ich war nicht in der Lage, den zusammenführenden Teil davon zu extrahieren. Es gelang mir, ein Merging-Netzwerk abzuleiten, das mir die minimal bekannte Anzahl von Vergleichsaustauscheinheiten für ein Sortiernetzwerk der Größe 24 gab, aber der Trick, den ich verwendete, war nicht auf andere Größen skalierbar (und meines Wissens war es das definitiv nicht) eine ungerade-gerade Zusammenführung).

Ich habe noch ein paar Dinge ausprobiert, um den Zusammenführungsschritt von Batchers ungeraden-geraden mergesort für Arrays anzupassen, deren Größe keine Zweierpotenz ist, aber ich konnte die bekanntesten Sortiernetze für die Größe 25 nicht finden. 26, 27, 28, 29 und 30. Wie kann ich diesen Zusammenführungsschritt ableiten, um die fehlenden Teile des Puzzles zu finden?