单核CPU情况下的集合排序
现存的Java集合排序例行程序没有异常。它们运行在一个新的多核机器上并不比一个单核机器上快。对于输入数据少的情况，这似乎是可以接受的，但是大多数现实世界的问题所需要的数据很大，那么这就是不能忍受的。另外，开发者和用户都希望他们的程序能够在新的硬件上运行得更快。
看看那些操作集合的一般算法，和现有的Java实现，将会澄清这个问题，并且会指明一条找到正确解决方案的道路。
算法的复杂度
大多数操作集合的核心算法都能在Arrays 和Collections 类中找到。使用这两个类中的API，你可以你可以对list和array排序，查找，填充。因为大多数的API操作整个集合的内容，整个运行时间和集合的大小成比例。
对于一些方法(如排序)，运行时间甚至更长。你不能在数步之内排序一个任意的集合，它是和集合的大小成比例的。这通常就称为线性复杂度。如果集合的大小是N，对这个集合进行排序的最好算法所需要的步骤数与N*log(N)成比例；这个下界被理论证明过。(注：对于冒泡排序所需要的步骤数与N*N成比例，这对于大的集合来说，是非常不适合的。)
对于一些方法(如排序)，运行时间甚至更长。你不能在数步之内排序一个任意的集合，它是和集合的大小成比例的。这通常就称为线性复杂度。如果集合的大小是N，对这个集合进行排序的最好算法所需要的步骤数与N*log(N)成比例；这个下界被理论证明过。(注：对于冒泡排序所需要的步骤数与N*N成比例，这对于大的集合来说，是非常不适合的。)
Java实现排序算法
查看Array 和Collection类中的各种的排序算法现在很容易，因为有他们都有开源许可证。Array中的所有排序例程都是使用快速排序法操作基本类型（如byte, char, double），快速排序通常被认为是最快的排序算法。（在很少的情况下，快速排序的性能下降到平方的程度。）操作对象数组的排序API使用的是归并排序，这种方法实现起来更为简单，而且性能也能达到N*log(N)的级别。最终，对于调用Collections.sort(List)，实际上是用Arrays.sort(Object[])来排序。
在进一步查看Array类中的归并排序，你可以看到它实际上是针对几个少数情况，对经典的归并排序做了几个优化。如果你的数组规模很小，它就退回到使用冒泡排序。否则，就是使用归并排序。
回到硬件发展，你可以轻松看到CPU增加的速度，改进了算法运行的时间。由于归并算法是一个顺序递归算法，有着完全一样的顺序步骤，提供相同的输入。
