Bug 41: Batcher's Merge Exchange Sort (Sort Of)
- This is a sorting method suitable for GPUs: Algorithm 5.2.2M from The Art of Computer Programming.
- The sort has a series of stages. All the inner loop iterations of a stage may be done in parallel.
- This implementation spreads inner loop iterations across goroutines instead of across GPU threads.
- It takes as input a slice to be sorted and the base 2 logarithm of the number of worker goroutines.
- Each stage has some number of iterations (all). Each worker does a range of consecutive iterations.
- Iterations for a stage are divided equally among workers, leaving a number of remainder iterations.
- The remainder iterations are assigned to some workers, with each worker responsible for at most 1.
- A barrier synchronization scheme ensures that each stage is complete before the next stage begins.
Fix The Tiny Bug In This Go Code: