분류 | 정렬 알고리즘 |
---|---|
자료 구조 | 배열 |
최악 시간복잡도 | 병렬 시간 |
최선 시간복잡도 | 병렬 시간 |
평균 시간복잡도 | 병렬 시간 |
공간복잡도 | 비병렬 시간 |
배처 홀짝 병합 정렬(Batcher odd–even mergesort, Batcher's odd–even mergesort[1])은 켄 배처가 크기 O(n (log n)2)와 깊이 O((log n)2)의 정렬망을 위해 고안한 구조이다. 여기서 n은 정렬할 항목의 수이다. 점근적으로 최적화된 것은 아니지만 도널드 커누스는 1998년 AKS 네트워크와 관련하여 "n이 지구상의 모든 컴퓨터의 총 메모리 용적을 초과하지만 않는다면 배처의 방식이 훨씬 더 낫다"고 밝혔다.[2]
그래픽 처리 하드웨어에서 효율적인 정렬을 하는 쉬운 방법으로서 2번째 서적 GPU Gems에 의해 보급되었다.[3]
# note: the input sequence is indexed from 0 to (n-1)
for p = 1, 2, 4, 8, ... # as long as p < n
for k = p, p/2, p/4, p/8, ... # as long as k >= 1
for j = mod(k,p) to (n-1-k) with a step size of 2k
for i = 0 to k-1 with a step size of 1
if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2))
compare and sort elements (i+j) and (i+j+k)