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:

1. Split the array into two halves: In this step, the array is divided into two halves for sorting.

2. Sort each half: The first half is sorted in ascending order and the second is in descending order, to make it the bitonic sequence.

3. Merge the sorted halves: Both halves of the arrays are then sorted in ascending or descending order accordingly.

4. 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:

Code example

Let’s implement the Python code of bitonic sort in the following playground:

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

1. Bitonic sort is highly suitable for parallel machines.

2. The algorithm of bitonic sort is simple to understand and implement.

3. It has a time complexity of $O(nlogn)$, which is similar to merge sort and other efficient sorting algorithms.

Limitations

1. 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.

2. The bitonic sort is not an in-place sorting algorithm, which means it requires extra space to sort the data.

3. 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:

Conclusion

The bitonic sort has significant importance in parallel computing architectures, although it’s not widely used. It’s efficient to use the bitonic sequence to sort the data, which makes it a valuable addition to the sorting algorithm family. It can be a good choice in modern-day computing applications due to its unique characteristics and sorting principles.