Bitonic Sort Algorithm

Introduction to Bitonic Sort

Bitonic sort is a parallel sorting algorithm that works by recursively constructing a bitonic sequence (a sequence that is first monotonically increasing and then monotonically decreasing) and then merging the sequence into a sorted one. It is particularly effective in parallel computing environments. Bitonic sort has a time complexity of O(log^2 n) when implemented in a parallel setting.

---

Step-by-Step Process

Consider an array with the following elements:

[3, 7, 4, 8, 6, 2, 1, 5]

To sort this array using bitonic sort, follow these steps:

1. Create Bitonic Sequence: Recursively divide the array into two halves, sorting the first half in ascending order and the second half in descending order.
2. Bitonic Merge: Recursively merge the bitonic sequences by comparing and swapping elements to create a single sorted sequence.
3. Repeat: Continue the process until the entire array is sorted.

Let's apply these steps to the example array:

• Initial array: [3, 7, 4, 8, 6, 2, 1, 5]
• Create bitonic sequence: [3, 7, 4, 8] (ascending), [6, 2, 1, 5] (descending)
• Bitonic merge: [3, 4, 7, 8, 1, 2, 5, 6]
• Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8]

---

Pseudo Code for Bitonic Sort

Below is the pseudo code for the bitonic sort algorithm:

function bitonicSort(array, low, cnt, direction)
    if cnt > 1 then
        k = cnt / 2
        bitonicSort(array, low, k, 1)
        bitonicSort(array, low + k, k, 0)
        bitonicMerge(array, low, cnt, direction)
    end if
end function

function bitonicMerge(array, low, cnt, direction)
    if cnt > 1 then
        k = cnt / 2
        for i = low to low + k - 1 do
            if (direction == 1 and array[i] > array[i + k]) or
               (direction == 0 and array[i] < array[i + k]) then
                swap(array[i], array[i + k])
            end if
        end for
        bitonicMerge(array, low, k, direction)
        bitonicMerge(array, low + k, k, direction)
    end if
end function

Explanation:

• Initialize: The bitonicSort function starts by checking if the count (cnt) is greater than 1. If true, it divides the array into two halves and sorts them in ascending and descending order respectively.
• Bitonic Merge: The bitonicMerge function recursively merges the bitonic sequences by comparing and swapping elements based on the direction (1 for ascending, 0 for descending).
• Repeat: The process repeats until the entire array is sorted.

---

Python Program to Implement Bitonic Sort

def bitonic_sort(arr, low, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        bitonic_sort(arr, low, k, 1)  # Ascending order
        bitonic_sort(arr, low + k, k, 0)  # Descending order
        bitonic_merge(arr, low, cnt, direction)


def bitonic_merge(arr, low, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        for i in range(low, low + k):
            if (direction == 1 and arr[i] > arr[i + k]) or (direction == 0 and arr[i] < arr[i + k]):
                arr[i], arr[i + k] = arr[i + k], arr[i]
        bitonic_merge(arr, low, k, direction)
        bitonic_merge(arr, low + k, k, direction)


def sort(arr, n, up):
    bitonic_sort(arr, 0, n, up)


# Example usage:
array = [3, 7, 4, 8, 6, 2, 1, 5]
print("Original array:", array)
sort(array, len(array), 1)
print("Sorted array:", array)  # Output: [1, 2, 3, 4, 5, 6, 7, 8]

This Python program defines functions to perform bitonic sort on an array. The bitonic_sort function creates the bitonic sequence, and the bitonic_merge function merges the sequences to create a sorted array. The sort function initializes the process by calling bitonic_sort with the entire array.