Bitonic Merge Sort is the military veteran uncle in the family.
He's very rigid, set in his ways; he'd much prefer that the world stop changing and adhere to his ideals for once, because then we'd all be better off. The way he sees it, the world is black-and-white, right-and-wrong, and there's a clear answer to every question. This is probably the reason why he doesn't get along with Bead Sort.
That said, he's a bit of a softy. He'll sneak Werther's Originals for his young grand-nieces and grand-nephews even after their parents have told them no, and has more than once spoken about how proud he is of grand-nephew Comb Sort's athletic ability. He's even offered to help grand-niece Counting Sort study so that she can keep her athletic scholarship. But at the end of the day, he's a man who holds strongly to his beliefs and is willing to defend them, no matter the cost.
The Rundown
- Created By: Ken Batcher
- Type: Concurrent
- Stable? No
- Best-Case: O(log2(n))
- Average-Case: O(log2(n))
- Worst-Case: O(log2(n))
- Space Complexity: O(n log2(n))
- Sample Project: Over on GitHub
exceptionnotfound
Algorithm
- SPLIT the array into two equal halves.
- SORT the left half in ascending order, and the right half in descending order.
- FOR EACH half of the array...
- ...GO TO 1 (using the half of the array as the new "base" array), RECURSIVE CONTINUE until the split array size is 1.
- MERGE all sorted subarrays back together.
Visualization
This is a difficult algorithm to visualize. The most important thing we need to know is that this algorithm makes a big assumption: that the unsorted array size is a power of 2 (e.g. 4, 8, 16, 32, etc). The algorithm only works in such cases.
Wikipedia uses this visualization of an eight-input bitonic sorter:
The idea is that inputs flow from left to right, "entering" the sort on the left and "exiting" on the right. At each "intersection" the two connected numbers are compared. If they are out of order, they are swapped.
Let's imagine we are using the following array
{ 81, 12, 19, 53, 39, 7, 2, 45 }
I found it much easier to visualize this algorithm if I added the numbers to the sorting array after each sorting step. That resulted in this image:
Each "phase" in this diagram represents a step in the algorithm. The numbers represent the current position of the array elements after each phase.
Please note that this visualization does not match the algorithm above or the implementation below, though all are permutations of the same ideas.
Finally, here's the "audibilization" of this sort, termed Batcher's Bitonic Sort in the video:
C# Implementation
class BitonicMergeSort
{
static void Swap<T>(ref T leftHandSide, ref T rightHandSide)
{
T temp;
temp = leftHandSide;
leftHandSide = rightHandSide;
rightHandSide = temp;
}
static void CompareAndSwap(int[] array, int i, int j, int direction)
{
int k;
k = array[i] > array[j] ? 1 : 0;
//If the order the elements are currently in DOES NOT match
//the sort direction (array[i] > array[j])...
if (direction == k)
{
//...Swap the elements so they DO match the sort direction
Swap(ref array[i], ref array[j]);
}
}
//This method recursively sorts a bitonic sequence in ascending order,
//if dir = 1, and in descending order otherwise (means dir=0).
//The sequence to be sorted starts at index position low,
//the parameter count is the number of elements to be sorted.
static void BitonicMerge(int[] array, int low, int count, int direction)
{
if (count > 1)
{
int k = count / 2;
for (int i = low; i < low + k; i++)
{
CompareAndSwap(array, i, i + k, direction);
}
BitonicMerge(array, low, k, direction);
BitonicMerge(array, low + k, k, direction);
}
}
//This function first produces a bitonic sequence by recursively
//sorting its two halves in opposite sorting directions, and then
//calls BitonicMerge to make them in the same direction
static void BitonicSort(int[] array, int low, int count, int direction)
{
if (count > 1)
{
int k = count / 2;
// sort left side in ascending order
BitonicSort(array, low, k, 1);
// sort right side in descending order
BitonicSort(array, low + k, k, 0);
//Merge entire sequence in ascending order
BitonicMerge(array, low, count, direction);
}
}
public static void Main()
{
int[] array = { 66, 98, 11, 43, 7, 28, 14, 49, 77, 61, 31, 12, 71, 93, 15, 2 };
int length = array.Length;
Console.WriteLine("Bitonic Merge Sort");
CommonFunctions.PrintInitial(array);
BitonicSort(array, 0 /*low value*/, length, 1);
//1 is for sorting in ascending order
CommonFunctions.PrintFinal(array);
Console.ReadLine();
}
}Time and Space Complexity
The time complexity for this algorithm is the same across all cases: O(log2(n)). This signifies that the size of the array and other conditions do not change the time needed, a very good thing in a sorting algorithm.
However, this is only true because the algorithm makes a major assumption: it assumes the input array has a length that is a power of 2. We see in this algorithm, as in others that make assumptions about their input, that those assumptions are what cause the improved performance many of them have. This is not a general-case sorting algorithm; this is a specialized one.
Summary
Bitonic Merge Sort is a very performant sort, provided the input size is a power of 2. Its consistent time complexities make it ideal for small or large sets of data. Plus, he's always got some Werther's. Maybe he'll even give you one.
The next family member at the reunion is the baby brother, Pigeonhole Sort, and he's a master of getting other people to do things for him.
Matthew Jones
Don't forget to check out the sample project over on GitHub!
Happy Coding!
