배처 홀짝 병합 정렬

배처 홀짝 병합 정렬(Batcher odd–even mergesort, Batcher's odd–even mergesort)은 켄 배처가 크기 O(n (log n)2)와 깊이 O((log n)2)의 정렬망을 위해 고안한 구조이다. 여기서 n은 정렬할 항목의 수이다. 점근적으로 최적화된 것은 아니지만 도널드 커누스는 1998년 AKS 네트워크와 관련하여 "n이 지구상의 모든 컴퓨터의 총 메모리 용적을 초과하지만 않는다면 배처의 방식이 훨씬 더 낫다"고 밝혔다.D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. . Section 5.3.4: Networks for Sorting, pp. 219–247.

그래픽 처리 하드웨어에서 효율적인 정렬을 하는 쉬운 방법으로서 2번째 서적 GPU Gems에 의해 보급되었다.

 의사 코드 
# 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)

 각주 

 외부 링크 
 Odd–even mergesort  at fh-flensburg.de
 Odd-even mergesort network generator Interactive Batcher's Odd-Even merge-based sorting network generator.

분류:정렬 알고리즘