Comparison-based Sorting Flashcards
What is a sorting network?
A fixed circuit that sorts its inputs using a special gate called a “comparator”
Describe the increasing/plus comparator and the decreasing/minus comparator
Given two inputs x and y, the plus comparator will put the smaller of the two elements “on the top wire” (remember, this is a circuit!) and the larger on the bottom. You can think of it like this: the “increasing” comparator pushes min(x,y) up to the top and max(x,y) to the bottom, so they are now in increasing order as you move from top to bottom.
The minus comparator does the opposite, pushing the smaller of the two elements to the bottom wire and the larger to the top. Now they are in decreasing order from top to bottom.
How can you use comparators to sort more than two items?
You can compose them! Like connecting wires in a circuit.
The neat thing here is that, if we can encode something as a circuit, we can then analyze it in terms of work (number of operations) and span (depth).
What is a bitonic sequence?
Recall that a monotonic sequence is strictly non-decreasing or non-increasing.
A bitonic sequence on the other hand is initially non-decreasing then at some point becomes non-increasing (or the other way around). Basically it goes up then down, or down then up.
OR (this is important), the sequence looks like this after some “circular shift”.
To see if it fits the bitonic definition given a circular shift, you can imagine the elements of the sequence on a ring (which connects the last element to the first). If you were to draw a + for every non-decreasing step and a - for every non-increasing step, the sequence is bitonic iff all + are consecutive and all - are consecutive, like +++—.
What is a circular shift?
Given a tuple, say (a, b, c, d), a circular shift is when you move the last item to the first position, then shift everything else to the right, like (d, a, b, c).
What is a bitonic split?
Given a bitonic sequence (assuming up then down for example), you get a bitonic split by pairing the first element of the “up” subsequence with the first element of the “down” subsequence, etc.
Example: Given (1, 3, 6, 5, 4, 2), a bitonic split would pair 1 and 5, 3 and 4, and 6 and 2.
Why is the bitonic split helpful for sorting?
Once you get the bitonic split, you can divide the original sequence into two new bitonic subsequences.
If we imagine an original sequence like (1, 3, 6, 5, 4, 2), the pairs would be 1 and 5, 3 and 4, and 6 and 2. If we take the min of each pair we get subsequence (1, 3, 2) and if we take the max we get (5, 4, 6), which are both bitonic sequences themselves! Further, they’re bitonic subsequences where every item in the min sequence is less than every item in the max sequence.
This allows for us to divide and conquer. And the split can happen in place! No need for extra storage (I guess this is because we can do all of this by just having pairs of elements switch places?).
Why does a parallel for loop have log(n) span (for n inputs)?
Because our main thread spawns a worker in step one, then each of those spawns a new thread, and each of THOSE spawns a new thread. So it takes x steps to create n threads, where 2^x = n and log_2(n) = x.
What is bitonic merge?
A parallel algorithm for sorting.
It’s when you start with a bitonic sequence and sort it using bitonic splits. The bitonic split always results in two halves, one less than the other. So basically you do the bitonic split, split again recursively on each half. You keep doing this until you have one item per group.
What is the pseudoscode for bitonic merge?
Let A be a bitonic sequence
def bitonicMerge(A[0:n-1]):
if n>=2:
bitonicSplit(A)
bitonicMerge(A[0 : n/2 - 1])
bitonicMerge(A[n/2 : n - 1])
How do you get a bitonic sequence for sorting in the first place??
You can take a sequence of arbitrary order by running bitonic merge for on the pairs of items that are next to each other, then groups of 4, then groups of 8, until you’ve gotten your bitonic sequence!
See 12. Generate a Bitonic Sequence in the Comparison-based Sorting lectures if this doesn’t make sense!
How does bitonic sort work on an arbitrary sequence?
Two steps: create a bitonic sequence by using bitonic merge on progressively larger chunks (pairs of two, groups of 4, etc). Then run bitonic merge on the resulting bitonic sequence!
What are the work and span of bitonic sort?
Why??? Add the reasoning! I imagine it has something to do with a par-for.
W(n) = Theta(n log^2 n)
D(n) = Theta(log^2 n)
The span here is poly-logarithmic which is great! But the algorithm is NOT work-optimal (i.e., the work of bitonic sort is not proportional to the work of the best sequential algorithm for this problem).
If bitonic sort isn’t work-optimal, then what’s the point?!
It has a fixed, natural, parallel structure. This means that if you have access to the right hardware (GPUS, FPGAs whatever they are, etc.) you can really take advantage of this parallelism.
But that also means there’s a tradeoff. So in the real world, it’s best to implement this algorithm alongside the best sequential algorithms and see which performs best on your hardware.
