Sorting methods with a fixed sequence of compare-exchange steps (sorting networks), such as bitonic sort, are sometimes used for sorting on parallel hardware such as GPUs. Why?

Answer: C. Which pairs of elements are compared and swapped is fixed in advance regardless of the data values, so many threads can work in the same steps at the same time with uniform branching

In bitonic sort, the pairs compared at each stage are determined by their indices alone, and all compare-exchange operations within a stage can run at the same time. n = 2ᵏ items are sorted in k(k+1)/2 stages: 16 items take 10 stages and 80 comparisons in total, and 1,024 items take 55 stages and 28,160 comparisons. The total number of comparisons is O(n log² n), more than quicksort and similar algorithms, but because the steps do not depend on the data, devices like GPUs, where many threads execute the same instructions, run them efficiently without divergent branches. No method that sorts by comparisons alone can use fewer than O(n log n) comparisons, and bitonic sort is generally not stable either.

• A. No comparison sort can do better than O(n log n) comparisons; bitonic sort makes O(n log² n) comparisons in total.
• B. Bitonic sort also swaps elements that are far apart, so it is generally not stable.
• C. Correct. Because the steps do not depend on the data, many threads can process them simultaneously with uniform branching.