Ungerade-Gerade-Vertauschungs-Sortierung
Bei der Aktivität „Das weltgrößte Sortiernetzwerk“ wird ein Sortiernetzwerk benutzt, das im berühmten Buch „The Art of Computer Programming“ von Donald Knuth, erwähnt wird. Knuth nannte dieses Netzwerk „Ungerade-Gerade-Vertauschungs-Sortierung“. Dort gibt er auch eine Formel zur Berechnung der Anzahl der Vergleichsknoten an: (1/2)n(n-1) Bei n Eingangsknoten besitzt es n Vergleichsebenen mit insgesamt (1/2)n(n-1) Vergleichsknoten, plus […]