↑ arvau

Wikipedia / Bitonic sorter

Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. is the number of items to be sorted. This makes it a popular choice for sorting large numbers of elements on an architecture which itself contains a large number of parallel execution units running in lockstep, such as a typical GPU.

A sorted sequence is a monotone

A bitonic sorter can only sort inputs that are bitonic. Bitonic sorters can be used to build a bitonic sort network that can sort arbitrary sequences by using the bitonic sorter with a sort-by-merge scheme, in which partial solutions are merged using bigger sorters.

.

Bitonic Sorter

is simply a comparator. This is illustrated by the given box layout, in which X and Y represent the inputs, while H and L represent the higher and lower outputs, respectively.

bitonic sorter.

by ensuring that each comparator always accepts one input from each of the two halves of the bitonic sequence it is meant to help sort. The following illustration depicts these connections schematically.

As you can see, elements of the first half of the input sequence are pairwise compared against corresponding elements of the last half of the input sequence. Comparing each element of the (green) subsequence with the element of the other (orange) subsequence at the respective index produces two bitonic subsequences. These two bitonic series (blue and red, respectively) can then be fed into the next lower-order bitonic sorter. This can be done because all elements in the red sequence are guaranteed to be higher than all elements in the blue series.

Correctness of the bitonic sorter

Ken Batcher provided some mathematical proof sketch in his paper..

Case 1 are trivially bitonic.

Case 2. Therefore, we now know that:

1

2

In the original paper he then claims the following inequalities result from those definitions:

Following from 1:

Following from 2:

are in fact bitonic.

Bitonic Sorting Networks (Bitonic Merge Sort)

bitonic sort network.

networks; hence, they are just a comparator. The following figure shows the overall scheme.

This overall scheme requires the sorter to have an input of sequence that is a power of two. There are, however, possibilities to mitigate this by, for example, using sentinel values.

Pseudocode

The following pseudocode describes the sorting process. In the code, a is the array to be sorted, low is the index of the first item in the sub-array to be sorted, k and count is the number items in the sub-array that are being sorted in this function call. direction is a boolean value that determines whether the sub-array is being sorted into ascending / descending order.

The function call bitonicSort(a, 0, n, 1) is used to sort a (ascending), where n is the number of items in a .

function bitonicMerge(a, low, count, direction) is
    if count > 1 THEN
        k ← count / 2
        // Compare and swap elements across the halves
        for i ← low to low + k do
            // determine if two elements of a are out of order in relation to the direction of sorting. 
            if (direction == 1 AND a[i] > a[i + k]) OR (direction == 0 AND a[i] < a[i + k]) THEN
                swap a[i] with a[i + k]

        // Recursively merge both halves
        bitonicMerge(a, low, k, direction)
        bitonicMerge(a, low + k, k, direction)

// This only works when input size is a power of 2.
function bitonicSort(a, low, count, direction) is
    if count > 1 THEN
        k ← count / 2

        // Sort first/second half into ascending/descending order
        bitonicSort(a, low, k, 1)
        bitonicSort(a, low + k, k, 0)

        // Merge entire sequence in desired order
        bitonicMerge(a, low, count, direction)

Complexity

input elements as previously.

.

This sum can be reduced using the Gauss sum

. comparisons can be performed in parallel.

Although the absolute number of comparisons is typically higher than Batcher's odd-even sort, many of the consecutive operations in a bitonic sort retain a locality of reference, making implementations more cache-friendly and typically more efficient in practice.

See also

References