**Half-Cleaner.**

For size n input sequence, i-th input is connected with comparator with i + n/2 input,

for i = 1, 2, ... , n/2. We'll assume than n is even.

Half-Cleaner.

**Bitonic Sorter.**

Bitonic Sorter Construction Algorithm.

Using a Half-Cleaner & two smaller Bitonic Sorters we can Create a larger Bitonic Sorter recurrentially as shown on above image.

a Complete Bitonic Sorter Example.

Bitonic Sorting has use in Sorting with time complexity of O(log

^{2}n) - a 'good behavior' for parallel sorting algorithms.

For Sequential Sorting Algorithms, 'good behavior' is time complexity of O(n · log n).

Source: [4], Wikipedia.

See also: Sorting Nets, Comparing Net, Bitonic Sequence, Bitonic Sorting in Cryptography.

## No comments:

## Post a Comment