What is Bitonic sort?

The bitonic sequence is a sequence in which the numbers are in increasing order, and after a certain point, they start decreasing. For example, the sequence [1,3,5,4,2] is a bitonic sequence.

The bitonic sort is a comparison-based sorting algorithm that sorts by converting elements to the bitonic sequence. It was introduced by Ken Batcher in 1968 for parallel computing architectures. The basic working of bitonic sort is to split the array into bitonic sequences and then merge them in a bitonic manner until the array is sorted completely. It’s a better choice for parallel implementation because it compares the elements in a predetermined sequence.

Algorithm steps

Let’s list down the steps of bitonic sort:

Split the array into two halves: In this step, the array is divided into two halves for sorting.
Sort each half: The first half is sorted in ascending order and the second is in descending order, to make it the bitonic sequence.
Merge the sorted halves: Both halves of the arrays are then sorted in ascending or descending order accordingly.
Repeat until the array is sorted: This process is repeated recursively until the array is sorted in the desired order.

Play the following slides to visualize the working of the bitonic sort:

def bitonic_sort(array, asc=True):
    def bitonic_merge(array, p1, mid, p2, asc=True):
        n = p2-p1
        temp_array = [0]*n
        i, j = p1, p2-1
        ind = 0 if asc else n-1
        step = 1 if asc else -1
        while i < mid and j >= mid:
            if array[i] < array[j]: 
                temp_array[ind]= array[i]
                i += 1
            else: 
                temp_array[ind] = array[j]
                j -= 1
            ind += step
        while i < mid:
            temp_array[ind]= array[i]
            ind += step
            i += 1
        while j >= mid:
            temp_array[ind] = array[j]
            ind += step
            j -= 1
        
        array[p1:p2] = temp_array
        return
    def sort(array, p1, p2, asc=True):
        if p2-p1 < 2: return
        mid = (p1+p2)//2
        sort(array, p1, mid, asc=True) # sorting the left subarray in ascending order
        sort(array, mid, p2, asc=False) # sorting the right subarray in descending order
        bitonic_merge(array, p1, mid, p2, asc) # merging both subarrays (the bitonic sequence)
        return
    
    sort(array, 0, len(array), asc=asc)
    return
array = [18, 13, 15, 11, 19, 12, 14, 16]
print("Unsorted array:", array)
bitonic_sort(array)
print("Sorted array in ascending order:", array)
array = [18, 13, 15, 11, 19, 12, 14, 16]
bitonic_sort(array, asc=False)
print("Sorted array in descending order:", array)

Code explanation

Let's discuss the code below:

Lines 2–26: We define a helper function bitonic_merge() that sorts the bitonic sequence. This function receives five arguments: array holds the actual array, p1 indicates the first index of the first subarray, mid indicates the center index, which is the first index of the second subarray, p2 indicates the boundary of the second subarray, and asc holds the boolean value that indicates to merge both subarrays in ascending or descending order. The subarray from p1 to p2 is the bitonic sequence. In this function:
- Line 3: We define a variable n and store the count of the elements to merge by subtracting p1 from p2.
- Line 4: We define a temporary array temp_array of size n.
- Line 5: We define two loops variables i and j, and assign them to the initial index p1 and the last index of the subarray p2-1, respectively.
- Line 6: We define a variable ind to store the index for the temp_array. We assign it a value of 0 (the first index) if the asc value is True, and n-1 (the last index) otherwise.
- Line 7: We define the variable step to move the ind forward or backward. We assign it the value of 1 if the asc value is True and -1 otherwise.
- Lines 9–16: We use the while loop to iterate through both subarrays. We compare the elements of the array at the ith and jth index and assign the required element to the temp_array at index ind. We increment the loop variable, and index variable ind accordingly.
- Lines 17–20: We shift the remaining elements of the first subarray to the temp_array.
- Lines 21–24: Similarly, we shift the remaining elements of the second subarray to the temp_array.
- Line 26: Lastly, we copy back the temp_array to the original array in the range of p1 to p2.
Lines 29–35: We define a function sort() that recursively sorts the array. This function receives four parameters: array, p1, p2, and asc. In this function:
- Line 30: We define the base case for the sort() function. The function returns if the elements are less than 2.
- Line 31: We find the center index mid by calculating the integer average of p1 and p2.
- Line 32: We call the sort() function to sort the array from p1 to mid in ascending order.
- Line 33: We call the sort() function to sort the array from mid to p2 in descending order. The array from the index p1 to p2 is now a bitonic sequence.
- Line 34: Finally, we call the bitonic_merge() function to sort the array from the index p1 to p2 in the given order asc.
Line 37: We call the sort() function to sort the complete array. We pass the array boundaries in the p1 and p2 variables. We also pass the asc to sort in the given order.
Lines 40–41: We create an unsorted array and print the array before sorting.
Lines 43–44: We call the bitonic_sort() function and print the array after sorting it in ascending order.
Lines 46–48: We reassign the same values to the array and call the bitonic_sort() function by passing the False value to the asc parameter. We print the array after sorting it in descending order.

Complexity

The time complexity of the bitonic sort is $O(nlogn)$ .

The space complexity of the bitonic sort is $O(n)$ .

Benefits and limitations

Let’s discuss some benefits and limitations of the bitonic sort.

Benefits

Bitonic sort is highly suitable for parallel machines.
The algorithm of bitonic sort is simple to understand and implement.
It has a time complexity of $O(nlogn)$ , which is similar to merge sort and other efficient sorting algorithms.

Limitations

The bitonic sort is not a stable sorting algorithm, which means it doesn’t guarantee that the order of similar elements in the sorted array will be maintained.
The bitonic sort is not an in-place sorting algorithm, which means it requires extra space to sort the data.
It’s not as widely used as other sorting algorithms, such as quicksort and merge sort, because it’s less efficient on sequential machines.

Bitonic sort vs. merge sort

The implementation of bitonic sort looks similar to merge sort, but it’s different in multiple ways. Let’s compare them in the following table:

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Merge sort	Bitonic sort
It uses the divide and conquer paradigm to sort the array.	It uses the bitonic sequence paradigm to sort the array.
It’s not naturally suitable and designed for parallel architectures.	It’s designed for parallel architectures.
It’s a stable sorting algorithm.	It’s not a stable sorting algorithm.
It’s widely used in different applications where stable and efficient sorting is required.	It’s not widely used as it was designed for parallel computing architectures.