说起内存排序，我立刻想到了大学和数据结构+算法设计老师的聊天，她推荐我去看《大道至简》，告诉我说，在很多复杂的情况下，先做内排序得到一个有序序列可以排除很多后续难题。我至今受用。

现在的计算机语言越来越高级，门槛越来越低，很多的基础细节再无人问津。万变不离其宗，作为科班出身的程序员，应该时刻温习基础知识。这里和大家一起从源码出发，看看Java中的排序是如何实现的。

还是先温习下内排序：

那么，java中到底是怎么排序的呢？它是使用的哪一种呢？首先，Java中用于给集合排序的API是，你只需要写个排序器或者实现排序接口，然后一句优雅的代码即可搞定排序，

• Collections.sort用于给List<T> 类型的对象集合排序
• Arrays.sort用于给T[]对象数组来排序

我们先来看看Collections.sort是怎么工作的，少废话，看源码。

Oh！天哪。Java很粗暴的直接用来list.toArray来把对象集合转化为对象数组，直接调用了Arrays.sort方法来sort，sort完成后再赋值回对象集合list中。那么，进一步探究，toArray干了什么？进一步看源代码，java中的list大家常用的是ArrayList和LinkedList，数组实现和链表实现。

• ArrayList：他非常暴力的直接新建了一个和list一样长度的数组，把ArrayList的data[]都copy了进去

• LinkedList：他也非常暴力的直接新建了一个和list一样长度的数组，然后采用了迭代器（Iteraotr）遍历一遍，把对象都copy了过去。

所以，从这里可以得出一个结论，编程过程中，如果能预知目标对象长度，请尽量使用对象数组来来管理多个对象，这里顺便补充些知识点，学过C的人都知道，想操作系统申请内存只能是一段连续的内存单元，编写过C语言的人对malloc和relloc函数很熟悉，一个拥有开辟一片内存，一个是追加内存。LinkedList我们都知道采用链表实现，无所谓浪费空间。ArrayList封装的就是一个数组private transient Object[] elementData; 那么ArrayList是怎么让你可以自由的add(T  t)的呢？我们也来看源代码，它在add方法中每次都要事先调用一句ensureCapacityInternal(size + 1);  // Increments modCount!! 即确保容量的过程，追溯代码如下：

这里是JDK1.7中的源码，JDK1.5之前，ensureCapcity算法有点不一样，但是也是类似，大家自行比较！

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); 这句话等价于 新的数组大小等于当前的大小乘以1.5,也就是增加50%

 

//如果新的大小比要求的最小容量小，则以最小容量为准，换言之，新容量=老容量+1
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;

 

//处理超大容量，如果对象巨大，达到了最大值（int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;）新数组大小就是 Integer.MAX_VALUE这么大，还不够，代码是OutOfMemoryError！！
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:

 

//最后是让我及其讨厌的内存复制，
elementData = Arrays.copyOf(elementData, newCapacity);
}

代码可以看得出，程序员在随意的add的时候，JDK随时在检查给你的对象集合扩容，这个扩展的速度十分可观，可以每次增加50%，如果你使用的构造函数是new ArrayList<YourDomain>，那么初始大小是10，此增长速度就是10*1.5的n次方。所以，这里建议大家：

如果你能预知和估算将要存的对象的数据，请使用new ArrayList<YourDomain>(size); 这会大大减少不断的扩充数组，复制对象….

如果你有频繁的中间插入对象，删除对象等等，请使用LinkedList

我们回到主题，来看排序算法问题，现在我们已经知道不管是Collection还是Array最终都是在Array上进行的排序。

我们看一下，jdk7中，进sort首先是一个if – else，说明一下，legacy的英文意思是遗留，这里的意思是，如果你想使用jdk5遗留的老排序算法的话，则使用老的MergeSort，否则使用新的TimSort，注意了，JDK5后排序算法有重大改进！如果你想在jdk5后的jdk中想继续沿用老的排序算法，则可以通过启动参数

-Djava.util.Arrays.useLegacyMergeSort=true

来强制使用遗留的MergeSort。

ok，接下来，我们的按JDK5以前（含5）的归并排序算法和JDK5后的算法分开讨论了。那么JDK5的归并排序算法，请自行看JDK的源码，

对于这个排序，这里无需多言，他是一个实实在在，纯的归并排序算法，只是在size<7，因为数组是在太小了，不需要浪费空间交换时间里，草草一个插入排序解决。

归并算法还记得么，温习一下，“归并排序是将两个或者多个有序序列合并为一个新的有序表”，系统采用的双路归并算法-将一维数组中前后相邻的两个有序序列归并为一个有序序列。

JDK6后的排序算法叫TimSort，一脸懵逼？什么是TimSort，没听过啊，看百科，别百度。 https://en.wikipedia.org/wiki/Timsort

从源码可以看得出，TimSort是一种杂和的排序算法，Java是怎么杂和的呢，上源码如下。

如果你仔细读以下源代码，你会发现其实他很简单，就是把数组分组排序，每组大小如果小于了MIN_MERGE-1=31个，这31个关键字采用binarySort，这个binarySort不做进一步解释，他是简单插入排序的简单改进型。

排序算法如何改进？请记住，尽你所能，

1. 减少关键字比较次数
2. 减少记录移动次数

binarySort就是在插入排序的比较关键字过程重不使用for循环，采用折半搜索快速跳跃的方式来比较关键字。就这么简单。

static void sort(Object[] a, int lo, int hi) {

//检查范围，防止数组越界问题
rangeCheck(a.length, lo, hi);
int nRemaining = hi – lo;//还剩下没有排的数组范围

 

//如果仅是1个没有排，显数组已经排好了，一个数他自身是有序的
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted

 

//如果这一段待排序的数组长度<32了，小规模的可以采用简单排序了，上binarySort

// If array is small, do a “mini-TimSort” with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}

 

/**
* March over the array once, left to right, finding natural runs,
* extending short natural runs to minRun elements, and merging runs
* to maintain stack invariant.
*/

//这里是核心算法，他采用了栈模拟递归的方法来做分块排序
ComparableTimSort ts = new ComparableTimSort(a);
int minRun = minRunLength(nRemaining);//计算最小的排序长度
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi);//计算下一趟运行的长度

// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;//还有一个强制的最小run的长度force
binarySort(a, lo, lo + force, lo + runLen);//足够小了，开始用小规模快读排序法-基于折半查找的插入排序法
runLen = force;
}

// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);//把排序的块信息压栈
ts.mergeCollapse();

//合并，这个很有意思，把栈元素进行合并，啥意思？很简单 某次排序 得到子序列如下：[2，3，5] [7,9,10],

//第一块的最大值比后一块的最小值小，这俩合并也是有序的。具体的看JDK注释，这是简单粗暴的解释！

// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);

// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();//还强制合并一下下
assert ts.stackSize == 1;//还下个断言,方便是方便，影响性能啊
}

 

那么，JDK为什么要摒弃MergerSort，转而改用TimSort呢？也很简单，事关时间和空间转换的法则，我们进入了大数据时代，CPU性能提高很多，MergerSort需要和原来一模一样大小的数据来最归并，这个新的空间复杂度和对象拷贝的过程相当损耗性能。

我们假设一下，一个程序员用了new ArrayList<>();没有指定初始大小，它存了200万个对象，ArrayList的elementData长度是850万，从200万+1到后面都是NULL。

那么MergeSort还没开始，它就要耗费：200万x4bytes = 7812.5K, 合计7.63M。 存对象的数组我理解为一个指针变量，按Int算，不算其他额外对象开销，然后还要花大量时间去Copy200万的对象到新数组，然后排序还没有开始。

TimSort适当的牺牲了时间性能，（我没有仔细测试，实际上不一定有牺牲），但是挽救了大量的内存消耗，性能大大提升。