多核环境的排序
当运行在一个多核的机器上时，现存的归并排序实现会有什么问题了？答案很简单：他不能对递归实现并行操作。当你的数组一分为二是，对第二个数组的排序是在第一个数组排序完成之后才开始的。但是新的JDK 6.0的出现解决了这个问题，能够让你并行的执行这些子任务，而不用它们之间的互相通信。最终，当两个任务都完成了，排序好了的两个数组仍旧需要合并在一起。它的复杂度仍然是N*log(N)，但是这一次的具有更低的不变因子。为了证明是如何低的，我将给你展示一个简单的归并排序的例子，利用多核的优点。这将带你进入并行程序设计的世界。
并行程序设计解决方案
下面将要演示的代码示例是基于核心JDK实现（通过GPL认证）基础之上的。第一步，如清单1所示，为了检查可用的处理器的数量。如果只有一个处理器的化，并行化的实现什么也不操作，你将为创建线程付出额外的开销。
清单1：输入规模小，并且是单处理器的特殊情况
if ((a.length < 7) || (Runtime.getRuntime().availableProcessors() == 1)) { mergeSort(aux, a, 0, a.length, 0); return; }
接下来你需要决定如何分配可用处理器的工作。为了简化实现的过程，我将只是在两个处理器之间划分工作。你很容易看到最终的合并阶段可以在两个一分为二的数组排序完成后进行。清单2使用了JDK 6.0中新的并行功能：
1. CountDownLatch类让你等待一个具体数目的、完成的任务（本例中是2）
2. Executors.newFixedThreadPool 运行两个排序线程
1. CountDownLatch类让你等待一个具体数目的、完成的任务（本例中是2）
2. Executors.newFixedThreadPool 运行两个排序线程
清单2：将一个排序分为两个单独而且并发的排序
final CountDownLatch doneSignal = new CountDownLatch(2); ExecutorService e = Executors.newFixedThreadPool(2); class WorkerRunnable implements Runnable { int start; int end; WorkerRunnable(int start, int end) { this.start = start; this.end = end; } public void run() { mergeSort(aux, a, start, end, 0); doneSignal.countDown(); } } int mid = a.length >> 1; e.execute(new WorkerRunnable(0, mid)); e.execute(new WorkerRunnable(mid, a.length)); try { doneSignal.await(); // wait for all to finish } catch (InterruptedException ie) { } e.shutdown();
待CountDownLatch.await返回结果，你就知道两个子任务都已经完成了。此时，你就可以合并排序好了的两个子数组，如清单3所示。
清单3：合并两个排序完成的字数组
System.arraycopy(a, 0, aux, 0, a.length); // merge two halves for (int i = 0, p = 0, q = mid; i < a.length; i++) { if (q >= a.length || p < mid && ((Comparable) aux[p]).compareTo(aux[q]) <= 0) a[i] = aux[p++]; else a[i] = aux[q++];
