Für das Sortieren auf paralleler Hardware wie GPUs werden manchmal Sortierverfahren mit einer festen Folge von Vergleichs- und Tauschschritten (Sortiernetzwerke) wie Bitonic Sort verwendet. Warum?

Antwort: C. Welche Elementpaare verglichen und vertauscht werden, steht unabhängig von den Datenwerten im Voraus fest; viele Threads können daher gleichzeitig dieselben Schritte ausführen, und die Verzweigungen bleiben einheitlich

Bei Bitonic Sort werden die in jeder Stufe verglichenen Paare allein durch ihre Indizes bestimmt, und alle Vergleichs- und Tauschoperationen innerhalb einer Stufe können gleichzeitig laufen. n = 2ᵏ Elemente werden in k(k+1)/2 Stufen sortiert: 16 Elemente brauchen 10 Stufen und insgesamt 80 Vergleiche, 1024 Elemente 55 Stufen und 28.160 Vergleiche. Die Gesamtzahl der Vergleiche ist mit O(n log² n) höher als bei Quicksort und ähnlichen Verfahren; weil die Schritte aber nicht von den Daten abhängen, führen Geräte wie GPUs, auf denen viele Threads dieselben Befehle ausführen, sie ohne divergierende Verzweigungen effizient aus. Kein Verfahren, das allein durch Vergleiche sortiert, kommt mit weniger als O(n log n) Vergleichen aus, und Bitonic Sort ist im Allgemeinen auch nicht stabil.