排序算法：归并排序

微信搜索【程序员囧辉】，关注这个坚持分享技术干货的程序员。

前言

这篇文章本该发表于2018年4月份末，在 排序算法：快速排序 之后，但是不知道什么原因，这篇文章忘了在CSDN上发表，今天在看博客的时候突然发现，因此补上。

概述

之前介绍过排序算法中效率很高的“快速排序”。本文将介绍另一个高效的排序算法——“归并排序”。

基本思想

归并排序的主要思想是分治法。主要过程是：

1. 将n个元素从中间切开，分成两部分。（左边可能比右边多1个数）

2. 将步骤1分成的两部分，再分别进行递归分解。直到所有部分的元素个数都为1。

3. 从最底层开始逐步合并两个排好序的数列。

思考

考虑一个问题，如何将两个有序数列合并成一个有序数列？

很简单，由于两个数列都已经有序，我们只需从两个数列的低位轮番拿出各自最小的数来PK就就行了，输的一方为小值，将这个值放入临时数列，然后输的一方继续拿出一个值来PK，直至有一方没有元素后，将另一方的所有元素依次接在临时数列后面即可。此时，临时数列为两个数列的有序合并。归并排序中的归并就是利用这种思想。对应的代码如下：

/**
 * 合并两个有序数列
 * array[first]~array[mid]为第一组
 * array[mid+1]~array[last]为第二组
 * temp[]为存放两组比较结果的临时数组
 */
private static void mergeArray(int array[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点
    int m = mid, n = last; // m为第一组的终点, n为第二组的终点
    int k = 0; // k用于指向temp数组当前放到哪个位置
    while (i <= m && j <= n) { // 将两个有序序列循环比较, 填入数组temp
        if (array[i] <= array[j])
            temp[k++] = array[i++];
        else