9/16/14

Merger.

Merger is a tool for merging two sorted sequences of the same length & of comparable data type(-s), into one sorted sequence.

For example: < 2, 3, 4 > can be merged with < 3, 5, 7 > into < 2, 3, 3, 4, 5, 7 >.

Merger uses Bitonic Sorter & part comparing i-th element with n - i + 1 for i = 1, 2, ..., n/2.



Merger Construction Algorithm, for n = 8.





Merger Example, for n = 8.



Merger has use in Parallel Sorting Algorithm with time complexity of O(log2 n).


See also: Bitonic Sorting Net.

Source: [4].

1 comment: