BUGFIX-66

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:

func mergeExchangeSort(a []int, lgWorkers int) { n := len(a) if n < 2 { return } top := 2 for top < n { top <<= 1 } top >>= 1 var ( pre = make( []chan struct{}, 1<<lgWorkers, ) post sync.WaitGroup ) worker := func(id int) { for p := top; p != 0; p >>= 1 { d, r := p, 0 for q := top; q >= p; q >>= 1 { <-pre[id] var ( all = n - d quo = all >> lgWorkers rem = all - quo<<lgWorkers at = quo * id do = quo ) if id <= rem { at += id do++ } else { at += rem } for i := at; i < at+do; i++ { if i&p != r { continue } lo, hi := a[i], a[i+d] if lo > hi { a[i], a[i+d] = hi, lo } } post.Done() d, r = q-p, p } } } for id := range pre { pre[id] = make(chan struct{}, 1) go worker(id) } for p := top; p != 0; p >>= 1 { for q := top; q >= p; q >>= 1 { post.Add(len(pre)) for _, pre := range pre { pre <- struct{}{} } post.Wait() } } }

To receive a hint, submit unfixed code.