Inbook,
Early History
chapter 1, page 1-7. Springer New York, (2011)
DOI: 10.1007/978-1-4614-1851-1_1
Abstract
The Bitonic Merge Sorting and the Odd–Even Merge Sorting algorithms are two parallel sorting algorithms. Both sort $N$ keys in no more than $łog_2 N$ steps with no more than $N/2$ comparators in each step. To sort $N$ keys using Bitonic Merge Sorting, firstly create two N/2 ordered lists: one in monotonic non-decreasing order and the other in monotonic non-increasing order. Then, apply bitonic merging to create two bitonic lists: H and L where H contains the largest $N/2$ keys and L contains the least $N/2$ keys. This would be repeated, recursively, until an N-key sorted list is generated. Odd–Even Merge Sorting of N-keys proceeds by merging two N/2 sorted lists A and B into the sorted list C. To do so, all the keys with odd indices in A and B are merged into one ordered list, D. Similarly, all the keys with even indices in A and B are merged into one ordered list, E. The first key in the output list C (i.e. c 1) would be the first key in D. Then, each two consecutive keys in C would be obtained by comparing the $i + 1$th key in D with the $i$th key in $E$.
