Let US sort

在这篇文章里，我尝试发掘 Go 语言的所有特性，以便用最优的、利用多核处理器的方式来实现 归并排序 。

时间复杂度为 O(nlogn) 的最优排序算法中，归并排序是其中之一。它的原理为将数组分为两部分，分别进行排序，最后再归并，这种做法的开销没那么大。

颜色说明：红色表示分割和排序，绿色表示归并

让我们通过代码演示最基本的形式：

图 1：数值表示数组元素形成的时间

func Sort(arr []int) []int {
	if(len(arr) <= 1) {return arr}
	mid := len(arr)/2
	s1 := Sort(arr[:mid])
	s2 := Sort(arr[mid:])
	return merge.Merge(s1, s2)
}

func update(final_arr []int, arr []int, index *int, increment_index *int) {
	final_arr[*index] = arr[*increment_index]
	*increment_index++
	*index++
}

func Merge(arr1 []int, arr2 []int) []int {
	size1 := len(arr1); size2 := len(arr2)
	final_arr := make([]int, size1 + size2)
	i := 0; j := 0; index := 0
	for ; i < size1 && j < size2; {
		if arr1[i] < arr2[j] {
			update(final_arr, arr1, &index, &i)
		} else {
			update(final_arr, arr2, &index, &j)
		}
	}
	for ; i < size1; {
		update(final_arr, arr1, &index, &i)
	}
	for ; j < size2; {
		update(final_arr, arr2, &index, &j)
	}
	return final_arr
}

观察可知，每个分割和归并的函数都是按照顺序执行的。

一个显而易见的优化方法是让 2 部分的排序并发执行，比如，如果长度为 2x 的 A 被划分为长度均为 x 的 X 和 Y，那么对 X 和 Y 的排序就可以并发地进行，因为同一内存地址不会被两个排序的线程访问。

func Sort(arr []int) []int {
	if(len(arr) <= 1) {return arr}
	mid := len(arr)/2
	var s1, s2 []int
	var wg sync.WaitGroup
	wg.Add(2)

	// Concurrency established
	Go func (s *[]int) {
		defer func() {wg.Done()} ()
		*s = Sort(arr[:mid])
	} (&s1)
	Go func (s *[]int) {
		defer func() {wg.Done()} ()
		*s = Sort(arr[mid:])
	} (&s2)
	// The sorting of arr[mid:] & arr[:mid] occurs Concurrently now.

	wg.Wait()
	return merge.Merge(s1, s2)
}

图 2：并发地排序，但是顺序地归并。数值表示元素形成的时间

这使得分割 / 排序的过程更为快速，因为并发地对每个子数组进行排序（希望能在多核之间并行地执行），但是归并的过程仍然被阻塞，等待子数组的排序完成。

观察可知，分割是并发进行的，但是归并要顺序地进行。

为了使整个过程都是并发的，我们不再等待每个子数组都完成排序，而是一有子数组完成排序就开始归并。

为什么更快？

...

/*
  update(f, a, &index, &i) =>
  f[index] = a[i];
  i++;
  index++;
*/
for ; i < size1 && j < size2; {
	if arr1[i] < arr2[j] {
		update(final_arr, arr1, &index, &i)
	} else {
		update(final_arr, arr2, &index, &j)
	}
}

...

回想一下，每次迭代中，归并的数组从每个已经排好序的数组中获取一个元素。如果每次比较的开销是 C，从子数组中重组一个长度为 N 的归并数组的开销将为 O(C*N) 。因此，如果最终数组的长度为 M，总的开销将为 ∑ C*(M+2*(M/2)+4*(M/4)+ … .) = C*M*log(M) is O(M*log(M)) ，因为每个归并操作要被阻塞，等到它的每个子数组都完成归并。

另一方面，并发的归并并不等到每一层完成后才进行，因此数组的值一被接收到就会向下传递。

注意，分割操作的复杂度为 O(1) 。

图 3：并发的归并，方框中的值代表其形成的时间

如何确保并发的归并？

Channels 可以用来传递和接收数据，因此一旦接收到初始元素，归并操作就会开始，不会被阻塞，等到之前的归并完成了才能进行。

func Sort(arr []int, ch chan int) {
	defer close(ch)
	if(len(arr) <= 1) {
		if(len(arr)==1) {
			ch <- arr[0]
		}
		return
	}
	mid := len(arr)/2
	s1 := make(chan int, mid)
	s2 := make(chan int, len(arr) - mid)

	// Concurrency established
	Go Sort(arr[:mid], s1)
	Go Sort(arr[mid:], s2)
	// The sorting of arr[mid:] & arr[:mid] occurs Concurrently now.

	// Merging happens simultaneously and is not blocked on individual sorting.
	merge.Merge(s1, s2, ch)
}

s1/s2 一接收到数据，它们就会进行处理然后把数据传递给 ch，ch 再将数据向下传递，以构造最终的数组。

func update(s chan int, ch chan int, c *int, ok *bool) {
	ch <- *c
	*c, *ok = <-s
}

func Merge(s1, s2, ch chan int) {
	// v, ok = <-s; ok returns false if there's no more element to be received from s.
	v1, ok1 := <-s1
	v2, ok2 := <-s2
	for ok1 && ok2 {
		if(v1<v2) {
			update(s1, ch, &v1, &ok1)
		} else {
			update(s2, ch, &v2, &ok2)
		}
	}
	for ok1 {
		update(s1, ch, &v1, &ok1)
	}
	for ok2 {
		update(s2, ch, &v2, &ok2)
	}
}

上面的过程和使用数组类似，但是现在使用的是 channels。

这个版本的归并排序开发了 Go 的所有特性，以此确保从排序到合并（不会阻塞直到完成）的并发性。正如现在你所猜测的那样，时间复杂度（假设是在多核的条件下进行，即可以有无数多个核来处理负载）从 O(N*log(N)) 下降到了 O(log(N)+N) ，即构造最终数组的时间复杂度是 N + 树的高度 ( logN )，也就是 O(N) 。

我没法说归并排序的时间复杂度是 O(N) ！

声明：多核处理器上最优化的归并排序可以将运行时间显著降为 O(N) 。

希望大家发现 Go 的美妙之处并为之做出贡献！