合并排序是您在CS课程大一学习的经典“分而治之”算法之一，对我来说，它是培养对递归和O(nlog(N))复杂性的直观感觉的最佳工具之一。
在这篇文章中，我们将检查Go中MergeSort的一个简单的并发版本，然后使用Go的简单基准测试工具，我们将查看它的问题所在，然后应用一个简单的修复。
如果你不熟悉这个算法，在哈佛的CS50.tv频道上有一个很好的解释：
基本思想是这样的：首先，像每个递归思想一样，我们假设我们手头有解决方案，并将其应用于输入的较小子集。在我们的例子中，有一个名为“MergeSort”的函数。然后，我们将MergeSort应用于输入的子集：我们将原始切片一分为二，并将左侧和右侧部分提供给相同的函数。
现在我们假设手中有两个排序的切片，左边和右边，我们需要合并它们(有趣的部分)。
因此，Merge函数用于合并两个排序的切片：这里的想法是将左侧的第一个元素与右侧的第一个元素进行比较。然后，根据所需的排序顺序(asc或desc)，我们取两者中较大(或较小)的一个，并将其附加到结果中。每次这样做时，我们都会截断从中获取附加元素的部分(因此，如果我们从左侧获取元素，那么左边的片段现在少了一个元素)，直到那里只剩下0个元素。
上面的MergeSort函数可以很容易地引入，并且具有一定的并发性。在第13-14行，我们有：
这是什么？同步计算？这需要一些大猩猩程序！让我们用某种并发性重写MergeSort，称之为MergeSortMulti：
很简单。对于递归的每一步，我们都将启动一个Goroutine来异步处理计算。然后，我们等待切片的两个部分的计算完成(这是同时进行的)，并合并结果。
这样肯定会更快，对吧？我们不必等到第一次递归结束后才开始第二次递归。不对!。
基准测试MergeSort与MegeSortMulti显示，前者，即同步版本，执行速度大约是并发版本的14倍。以下是切片中一百万个元素的基准测试代码：
它显示并发版本比正常同步版本慢得多：
到底怎么回事？看起来，在我们寻求使计算并发的过程中，我们正在疯狂地激发大猩猩程序。对于递归的每一步，我们触发两个Goroutine。这最终会产生数百万个使用GO的Goroutine排队机制争夺CPU的Goroutine。结果是代码变慢了。
那么，我们如何才能在不设置大量Goroutine的情况下获得并发代码的性能优势呢？嗯，在GO中限制并发性的一个很好的方法是使用缓冲的通道信号量。Go中的缓冲通道是根据我们希望拥有的并发操作单元的数量来阻止执行的一种很好且简单的方法。
我们设置一个容量为100的缓冲通道，当我们产生goroutines以执行异步计算时，如果已经有100个工作者(Goroutines)忙于计算，我们将恢复使用MergeSort的同步版本：