Bitonic Sort

Bitonic Sort
============


Bitonic sort is a sorting method that is very well suited for running in distributed systems because of the way the
algorithm is built.


Bitonic sequence
----------------

We should start by defining what a bitonic sequence actually is. A bitonic sequence if a list of numbers with the
property that, given K(i) the i'th element and N the length of the list, we have
    K(0) <= K(1) <= ... <= K(N/2 - 1) <= K(N/2) >= K(N/2 + 1) >= ... >= K(N - 1) OR
    K(0) >= K(1) >= ... >= K(N/2 - 1) >= K(N/2) <= K(N/2 + 1) <= ... <= K(N - 1)

This property gives us a very interesting leverage in sorting these numbers. Let's consider a list of random numbers
that are are bitonic sequence and try to see how we would go about sorting it.
Let's consider the following list:
    3 4 9 21 18 8 3 1
The list can now be split into two different pars: the ascending part and descending one, each of size four.
the way the algorithm works is that we take the first element of the first sequence (the ascending one) ad compare it
with the first element of the second sequence (the descending one) and if the first if greater then than the second, we
swap them. the visual representation of this process looks like this:
    3  4  9  21  18  8  3  1
    ------------->
       ------------->
          ------------->
                 ---------->

Each line represents a so called comparator to which the consequence may be a swap between the values that it is
comparing. So, given the bitonic sequence above, we would end up with the following sequence, after we have applied
the comparisons and the swapping:
    3  4  3  1  18  8  9  21

Now, if we look closely, we now 4 items sequences that can be considered bitonic:
    3  4  3  1      18  8  9  21
      /   \            \    /
     /     \            \  /

What we do with these is exactly the same as to what we did with the first bitonic sequence: we create comparators and
we swap accordingly, only that we bitonic sequences of smaller sizes:
    3  4  3  1  18  8  9  21
    ------>      ----->
       ------>       ----->
After we swap the necessary items we end up with bitonic sequences of size two which again can be compared and in the
end we are left with the sorted list.


Applying the algorithm on real life lists
-----------------------------------------


As one may think, we don't often find these kind, bitonic, sequences out there in the wild and we are more often made to
deal with ugly looking lists that also need sorting. In order to cope with those, a tweak was added to the algorithm so
that it can transform the list in a bitonic sequence, starting from small subsets of the list to the whole list.

As explained above, the algorithm starts from large to small, comparing and swapping. The actual sorting algorithm
starts by taking elements of the list, two by two in sets of two and transforming them in bitonic sequences and then
applies the algorithm above to merge them and end up with a subset of the whole list that is sorted.
It transforms a subset of the list into a bitonic sequence by, again, applying comparators only that in opposing
directions, as in the figure below; the direction of the arrow tells the direction of the comparator, to the right
ascending and to the left descending:
    5   89   3   32   34   23   6   1
    ---->     <----   ----->    <----


This will result in a new list which has two sets of bitonic sequences:
    5  89  32  3  23  34  6  1
      /      \      /       \
     /        \    /         \

On these sequences the algorithm we first explained is applied, for the first sequence in ascending order and for the
second in descending order transforming it again in a bitonic sequence that can be ordered.

The complexity of this algorithm is O(n long(n)^2).
The one limitation this algorithm has is that it can only be applied to lists that have a number of elements that is a
power of two.



Running Bitonic Sort in Parallel
--------------------------------

Bitonic Sort is a very well suited algorithm for parallel processing because of the recursive nature it has. For this
version, as well, the number of elements in the list must be a power to two and the number processes as well.

The algorithm works by spawning the required number of processes and evenly distributing the elements of the list among
all of them. After that, the algorithm defines a way to identify an pair up two processes that will work together and
exchange and compare data. After having this strategy, the algorithm begins and each process, together with it's partner
exchange lists. Each of these pairs if responsible for either getting the smaller number from the combined list of the
two or the higher numbers. Code looks something like this:

    int  index1 = 0;
    int  index2 = 0;

    for (i = 0; i < list_size; i++)
        if (my_list[index1] <= partner_list[index2]) {
            scratch_list[i] = my_list[index1];
            index1++;
        } else {
            scratch_list[i] = partner_list[index2];
            index2++;
        }
    for (i = 0; i < list_size; i++)
        my_list[i] = scratch_list[i];

So after they exchange lists, each of the processes takes the number they are supposed to take and holds them on for the
next stage. This process repeats a number of times which is calculated based on the number of processes involved and the
number of elements.


The parallel version of bitonic sort can run tens of times faster than the sequential sort given enough number of
processes. The nature of the algorithm allows for huge scaling and very high performances.