GPU 같은 병렬 처리 장치에서 정렬을 수행할 때, 바이토닉 정렬처럼 비교·교환 절차가 정해져 있는 정렬(정렬 네트워크)이 쓰이는 경우가 있다. 그 이유로 올바른 것은?

정답: C. 어느 원소 쌍을 비교·교환할지가 데이터 값과 관계없이 미리 정해져 있으므로, 많은 스레드가 같은 절차로 동시에 처리할 수 있고 처리의 분기도 일치하기 때문

바이토닉 정렬에서는 각 단에서 비교하는 원소 쌍이 첨자만으로 정해지며, 한 단 안의 비교·교환은 모두 동시에 수행할 수 있습니다. n = 2ᵏ개의 데이터는 k(k+1)/2단으로 정렬되며, 16개면 10단에 합계 80회, 1,024개면 55단에 합계 28,160회의 비교를 수행합니다. 비교의 총수는 O(n log² n)으로 퀵 정렬 등보다 많지만, 데이터에 따라 절차가 바뀌지 않으므로 GPU처럼 많은 스레드가 같은 명령을 실행하는 장치에서는 분기의 어긋남이 일어나지 않아 효율적으로 동작합니다. 비교만으로 정렬하는 방법은 O(n log n)보다 적은 비교로는 끝나지 않으며, 바이토닉 정렬은 일반적으로 안정적이지도 않습니다.