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 n Eingangsknoten und n Ausgangsknoten.

Für n=50 ergibt das 1325 Knoten

Für n=25 ergibt das 350 Knoten

Für n=25 ergibt das 252 Knoten

Knuth zeichnet Sortier-Netzwerke so, dass jeder Vergleich durch 2 Knoten dargestellt wird und es keine Knoten für Ein-/Ausgaben gibt.

Das ergibt:

n=50 -> 2450 Knoten
n=21 -> 420 Knoten
n=25 -> 600 Knoten

Donald Knuth

Seit einem halben Jahrhundert regiert der Stanforder Informatiker Donald Knuth als geistlicher Führer des algorithmischen Reiches. Mit mehr als einer Million Exemplaren im Druck ist „The Art of Computer Programming“ die Bibel seines Fachgebietes. Mehr dazu im Artikel der New York Times