Des méthodes de tri dont la suite d'étapes de comparaison-échange est fixée d'avance (réseaux de tri), comme le tri bitonique, sont parfois utilisées pour trier sur du matériel parallèle comme les GPU. Pourquoi ?

Réponse : C. Les paires d'éléments comparées et échangées sont fixées à l'avance, indépendamment des valeurs des données, si bien que de nombreux threads peuvent exécuter les mêmes étapes en même temps, avec des branchements uniformes

Dans le tri bitonique, les paires comparées à chaque étape ne dépendent que de leurs indices, et toutes les opérations de comparaison-échange d'une même étape peuvent s'exécuter en même temps. n = 2ᵏ données sont triées en k(k+1)/2 étapes : 16 données demandent 10 étapes et 80 comparaisons au total, et 1024 données 55 étapes et 28 160 comparaisons. Le nombre total de comparaisons est en O(n log² n), plus que pour le tri rapide et les algorithmes similaires, mais comme les étapes ne dépendent pas des données, les dispositifs comme les GPU, où de nombreux threads exécutent les mêmes instructions, les exécutent efficacement, sans branchements divergents. Aucune méthode qui trie uniquement par comparaisons ne peut faire moins de O(n log n) comparaisons, et le tri bitonique n'est en général pas stable non plus.