1 思路
假设有这样一个数组：
数组
归并排序的思路是，将这个数组先不断的拆分为二，直至只有一个子元素。然后不断的向上合并已排好序的子数组。
归并排序过程
因此，大概的流程是这样：
- 将一个大的数组分成两部分子数组
- 分别对两个子数组进行排序
- 将两个已排好序的子数组进行合并
- 大的数组也已经排好序了
因此，假设有一个函数，实现了上面的功能：
void sort(int[] aar, int l, int r) {
// 1.判断待排序数组空间是否合法
if (l >= r)
return;
int mid = l + (r - l) / 2;
// 2.对左边部分子数组进行排序
sort(aar, l, mid);
// 3.对右边数组进行排序
sort(aar, mid+1, r);
// 4.合并两部分数组
merge(aar, l, mid, r);
}
由以上分析可知，归并排序算法的核心在于实现merge函数，这也是该算法称为归并的原因。
2 实现
2.1 merge的实现
这里先实现merge。本质上，merge就是将两个已排好序的数组合并为一个排序数组，在这里只不过是将两个已排好序的子数组合并为一个更大的排序子数组。
使用k来遍历待排序的更大的子数组，用来放置合适的值。由于会发生值变换，因此需要先把数组中的元素拷贝一份。
使用i来遍历左半部分的已排序数组，使用j来遍历右半部分的已排序的数组。不断的将两部分i和j所指向的更小的元素拷贝到索引为k中。
代码如下：
// 数组data的区间[l .. mid][mid+1 .. r]分别是有序的，对这两个区间的元素进行合并排序
private static <E extends Comparable<E>> void merge(E[] data, int l, int mid, int r) {
E[] temp = Arrays.copyOfRange(data, l, r + 1);
int i = l;
int j = mid + 1;
// k轮询原数组待操作区域的索引，用于放入新元素
for (int k = l; k <= r; k++) {
if (j > r) {
data[k] = temp[i - l];
i++;
} else if (i > mid) {
data[k] = temp[j - l];
j++;
} else if (temp[i - l].compareTo(temp[j - l]) < 0) {
data[k] = temp[i - l];
i++;
} else {
data[k] = temp[j - l];
j++;
}
}
}
2.2 递归的实现
根据开始的伪代码，实现对应的Java代码
public static <E extends Comparable<E>> void sort(E[] data) {
if (data == null || data.length <= 1) {
return;
}
sort(data, 0, data.length - 1);
}
// 对数组data的区间[l .. r]进行排序
private static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
// 最简单的问题
if (l >= r) {
return;
}
// 先求解更小的问题
int mid = l + (r - l) / 2;
sort(data, l, mid);
sort(data, mid + 1, r);
// 根据最小问题的解解决当前问题
merge(data, l, mid, r);
}
3算法复杂度分析
复杂度分析
由以上图示可知，对于归并算法的每一层，归并所需要的操作的和都为8，推而广之为n，因此每一层的算法复杂度为O(n)。
接下来在看层数，由于每次会一分为二，这可以看成是一个树结构，它的层数的量级为logn。
因此归并排序算法的复杂度为O(nlogn)
4 优化
4.1 判断是否需要merge
如果两部分已排序子数组，后半部分的最小索引的元素比前半部分最大索引的元素要大，此时，不需要重新排序：
// 对数组data的区间[l .. r]进行排序
private static <E extends Comparable<E>> void sort2(E[] data, int l, int r) {
// 最简单的问题
if (l >= r) {
return;
}
// 先求解更小的问题
int mid = l + (r - l) / 2;
sort2(data, l, mid);
sort2(data, mid + 1, r);
// 根据最小问题的解解决当前问题
if (data[mid].compareTo(data[mid + 1]) > 0) {
merge(data, l, mid, r);
}
}
针对这个优化，做一个100,000规模数据的排序比较结果如下：
MergeSort: n = 100000, costTime: 0.060000S // 未优化
MergeSort2: n = 100000, costTime: 0.022000S // 已优化
可以看到，优化后的算法，在这个数据规模和我的电脑上，时间快了三倍。
另一方面，加入数组本来就是一个有序的，那么，将不会进入到merge过程，整个算法的复杂度将会退化到O(n)级别。
4.2 使用插入排序排序较小子数组
归并排序的merge算法相对来说操作步骤较多，当数据规模较小时，更有可能有序，插入排序算法的性能可能会更好，因此，我们假设当子数组数据量没超过16时，使用插入排序。
首先，重新定义一个插入排序方法，允许排序一个数组的子数组区间：
// 对数组data的区间[l, r]进行排序
public static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
// 第一重循环，维持循环不变量data[l ... i)中的元素都是已排好序的
for (int i = l; i <= r; i++) {
// 第二重循环，将data[i]中的元素插入到已排好序的正确位置，不是合适的位置的元素，都往后挪一个索引
E t = data[i]; // 待插入元素
int j; // 待插入位置
for (j = i; j - 1 >= l && t.compareTo(data[j - 1]) < 0; j--) { // 该重循环的工作是寻找待插入的正确位置j
data[j] = data[j - 1];
}
data[j] = t;
}
}
然后，再改进sort方法
// 对数组data的区间[l .. r]进行排序
private static <E extends Comparable<E>> void sort2(E[] data, int l, int r) {
// 最简单的问题
if (r - l <= 15) {
InsertionSort.sort(data, l, r);
return;
}
// 先求解更小的问题
int mid = l + (r - l) / 2;
sort2(data, l, mid);
sort2(data, mid + 1, r);
// 根据最小问题的解解决当前问题
if (data[mid].compareTo(data[mid + 1]) > 0) {
merge(data, l, mid, r);
}
}
和只是进行merge判断优化对比，在我的机子上针对100,000的数据，快了3倍多。
MergeSort: n = 100000, costTime: 0.073000S // merge判断优化
MergeSort2: n = 100000, costTime: 0.029000S // 进一步插入排序优化
4.3 一次性分配临时数组
在上面的实现中，每一次merge都会创建一个新的临时数组，这是非常耗性能的。我们可以一开始就定义一个的数组：
public static <E extends Comparable<E>> void sort2(E[] data) {
if (data == null || data.length <= 1) {
return;
}
E[] temp = (E[]) new Comparable[data.length];
sort2(data, 0, data.length - 1, temp);
}
// 对数组data的区间[l .. r]进行排序
private static <E extends Comparable<E>> void sort2(E[] data, int l, int r, E[] temp) {
// 最简单的问题
if (r - l <= 15) {
InsertionSort.sort(data, l, r);
return;
}
// 先求解更小的问题
int mid = l + (r - l) / 2;
sort2(data, l, mid, temp);
sort2(data, mid + 1, r, temp);
// 根据最小问题的解解决当前问题
if (data[mid].compareTo(data[mid + 1]) > 0) {
merge2(data, l, mid, r, temp);
}
}
// 数组data的区间[l .. mid][mid+1 .. r]分别是有序的，对这两个区间的元素进行合并排序
private static <E extends Comparable<E>> void merge2(E[] data, int l, int mid, int r, E[] temp) {
System.arraycopy(data, l, temp, l, r - l + 1);
int i = l;
int j = mid + 1;
// k轮询愿数组待操作区域的索引，用于放入新元素
for (int k = l; k <= r; k++) {
if (j > r) {
data[k] = temp[i++];
} else if (i > mid) {
data[k] = temp[j++];
} else if (temp[i].compareTo(temp[j]) < 0) {
data[k] = temp[i++];
} else {
data[k] = temp[j++];
}
}
}
在我的机子上，针对这样的优化的性能比较如下，可以看到，也是快了点：
MergeSort: n = 100000, costTime: 0.042000S // 已进行了前两步优化
MergeSort2: n = 100000, costTime: 0.037000S // 增加统一数组分配优化
自底向上归并排序算法
上面实现的归并排序算法，是将一个数组不断拆分成两个更小的数组，这样一种思路是一种自顶向下的。另一种相反的思路是自底向上的。
例如对于一开始的八个元素，先对每两个元素进行合并：
每两个元素进行合并
然后在进行每四个元素进行合并：
每四个元素进行合并
然后就是接下来，对所有8个元素进行合并。
实现代码如下，需要注意的是，当数组长度不为2的n次方的时候，对于merge的右边界值，需要和数组的边界做比较：
public static <E extends Comparable<E>> void sort(E[] data) {
if (data == null || data.length <= 1) {
return;
}
E[] temp = (E[]) new Comparable[data.length];
int n = data.length;
// 遍历合并的区间的长度
for (int sz = 1; sz < n; sz += sz) {
// 合并[i, i + sz -1]和[i + sz, Math.min(i + sz + sz - 1, n -1)]
for (int i = 0; i + sz < n; i += sz + sz) {
if (data[i + sz - 1].compareTo(data[i + sz]) > 0) {
merge(data, i, i + sz - 1, Math.min(n - 1, i + sz + sz - 1), temp);
}
}
}
}
