golang fast concurrent sorting

faster_sort.go

package main

import (
	"math/rand"
	"fmt"
	"time"
	"sort"
)

const N = 1 << 20
const B = 1 << 10 // num buckets
const M = N/B // size of bucket
var nums [N]int

func setNums() {
	rand.Seed(42)
	for i := 0; i < N; i++ {
		nums[i] = rand.Int()
	}
}

func sortNums() {
  // https://twitter.com/robertkingNZ
	ch := make(chan bool, B)
	sortBucket := func(bucket []int) {
		sort.Ints(bucket)
		ch <- true
	}
	for i := 0; i < B; i++ {
		go sortBucket(nums[i*M: (i+1)*M])
	}
	for i := 0; i < B; i++ {
		<- ch
	}
	merge := func(b1, b2, slice []int) {
		stack := make([]int, len(slice))
		i, j := 0, 0
		for k := range slice {
			if i == len(b1) {
				stack[k] = b2[j]
				j++
			} else if j == len(b2) {
				stack[k] = b1[i]
				i++
			} else if b1[i] <= b2[j] {
				stack[k] = b1[i]
				i++
			} else {
				stack[k] = b2[j]
				j++
			}
		}
		for k, v := range stack {
			slice[k] = v
		}
		ch <- true
	}
	b, m := B, M
	for b > 0 {
		for i := 0; i+1 < b; i += 2 {
			go merge(nums[i*m: (i+1)*m], nums[(i+1)*m: (i+2)*m], nums[i*m: (i+2)*m])
		}
		for i := 0; i+1 < b; i += 2 {
			<- ch
		}
		b /= 2
		m *= 2
	}
}

func main() {
	setNums()
	now := time.Now()
	sort.Ints(nums[:])
	fmt.Println("time: ", time.Since(now))
	setNums()
	now = time.Now()
	sortNums()
	fmt.Println("time: ", time.Since(now))
  // time:  246.302737ms
  // time:  109.264487ms   <--- 2x faster
}