归并排序算法是一种建立在分治法思想之上的排序算法，分治分治可以简单的理解为”分而治之“，核心思想就是将复杂的问题分为若干个子问题，使这些子问题都是原问题的规模较小的实例；然后解决这些较简单的子问题，最后将结果合并，从而得到最开始那个复杂的问题的答案。

归并排序的思想也是如此，步骤如下：

        一、将一个数组拆分为两个部分，一般取数组长度一般的位置为界，分为两个子数组，再分别对这两个子数组进行递归归并排序

        二、我们确信在进行完递归排序之后，原两数组都会分别变为各自排好序的两个数组，于是接下来我们进行将这两个子数组合并为一个数组的操作；对于最上层，这是最后一步完成排序的操作

        三、对于每一次分解出来的子数组，进行归并操作。

        只要数组的长度大于1，即数组的头元素的序数<子数组尾元素的序数，那么就继续递归拆分成更小的两个子数组，再继续进行归并排序。。。一直递归到某一次拆分的时候，两个子数组其中有一个数组只有一个元素。只有一个元素当然不需要进行排序了，于是进行数组的合并，由于合并的时候是按照两个子数组的元素大小顺序来合并的，所以会保证对于最底层的两个子数组合并（这里两个子数组中，至少有一个是单元素数组；而另一个数组为单元素数组或者双元素数组）会按照排好序的顺序给出合并之后的数组，这样一层一层上向上递归合并，最后得到的数组就是原始数组的排好序的版本了。

        图示：

        可能到这里还不甚理解，可以看看图，我们这里以比较容易看清过程的8元素数组为例，下图最底层为已经拆成单元素数组的原始数组：

下面我们一步一步来看看。

        算法核心实际上在于如何将两个数组合并的简单操作。我们可以简单的将两个数组看成两堆扑克牌，这里以从小到大排序为例。

        我们每次从两个数组中分别拿出一张牌来进行比较，将小的那一张放到第三堆（最开始为空）的堆里，然后将大的那一张牌扔回它原来的牌堆，然后再重复上述操作，直到有一堆牌被抽空为止。这时另一堆牌至少剩余一张，又因为这两堆牌原本就是按从小到大顺序排好的，所以我们这时只需要将还剩余牌的那堆牌简单的全部挪到第三堆牌里即可，这样就完成了所有牌的从小到大的排序工作了。

看看代码：

//合并两个数组，按从小到大，这两个数组已经排序好了的
/*
 * 合并两个数组
 */
void mergeArr2(int a[], int n, int b[], int m, int c[]) {

	int i = 0; //a数组
	int j = 0; //b数组
	int k = 0;
	while (i < n && j < m) {
		if (a[i] < b[j]) {
			c[k++] = a[i++];
		} else {
			c[k++] = b[j++];
		}
	}

	while (i < n) {
		c[k++] = a[i++];
	}
	while (j < m) {
		c[k++] = b[j++];
	}
}

        但是在这里这样写可能有些不合适，因为我们原来拿到的是一个数组，假设为int a[]，如果每次都要拆分成两个数组来传入的话难免有些麻烦；我们可以稍微改动一下，传入一个数组a，和数组c，然后传入我们a的头尾序数以及分割a为两个数组的那个序数，代码改为如下样子：

/*
 * 合并一个数组的两个部分：[start,mid]和[mid+1,end]；其中start和end分别为最前和最后的元素的下标，mid为中间的下标，由于mid=(start+end)/2，
 * 而且start<end，所以mid可能等于start，但是一定会小于end
 */
void mergeArr(int a[], int start, int mid, int end, int*tmp) {
	int i = start;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= end) {
		if (a[i] < a[j]) {
			tmp[k++] = a[i++];
		} else {
			tmp[k++] = a[j++];
		}
	}

	while (i <= mid) {
		tmp[k++] = a[i++];
	}

	while (j <= end) {
		tmp[k++] = a[j++];
	}

	cout << "k=" << k << endl;
}

        上面的代码虽然完成了合并，但是还有一个小问题，就是我们一般都希望合并完之后会是原来的int a[]数组是合并完且排好序的，而不是那个tmp数组，所以这里我们还需要在上面代码末尾加上一段，将tmp中的数拷贝到对应于a数组中的位置去：

void mergeArr(int* a, int start, int mid, int end, int*tmp) {
	int i = start;
	int j = mid + 1;
	int k = 0;
	while (i <= mid && j <= end) {
		if (a[i] < a[j]) {
			tmp[k++] = a[i++];
		} else {
			tmp[k++] = a[j++];
		}
	}

	while (i <= mid) {
		tmp[k++] = a[i++];
	}

	while (j <= end) {
		tmp[k++] = a[j++];
	}

	cout << "k=" << k << endl;

	//到这里为止，tmp就把a中两段子数组的内容合并，复制过来了，但是我们的目的是让a中这一段的数据能够也排好序的放好，所以最后还需要做一个工作，从tmp拷贝数组
	for (int i = 0; i < k; i++) {
		a[start + i] = tmp[i];
	}
}

这样，合并操作的代码就完成了，我们下面只需要按照之前的思路，写好归并排序的函数即可：

/*
 * 归并排序
 */
void mergeSort(int a[], int start, int end, int* tmp) {

	//start < end条件可以让子数组长度等于1时，不再进行归并排序
	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(a, start, mid, tmp);
		mergeSort(a, mid + 1, end, tmp);
		mergeArr(a, start, mid, end, tmp);
	}
}

        我们可以简单的看一下归并排序算法的时间复杂度，对于合并操作，每一次合并函数需要循环的次数是end-start+1 。

        这样看还是不甚清晰；我们不妨假设原始数组的长度n为2的次幂，于是分解到最后一层的时候，每一次merge操作的对象都是两个单元素数组，那么一次merge操作需要经历两次循环，最后一层有n/2次merge操作，于是需要经历n/2*2=n次循环；对于倒数第二层，每一次merge操作的对象是两个双元素数组，一次merge操作需要经历4次循环，本层需要经历n/4次merge操作，于是需要经历n/4*4=n次循环。。。依次类推，每一层都需要经历n次循环，而一共有多少层呢？我们最开始有n个数，每一层都要除以2，一直除到最后一层等于1个数组，假设有k层，于是2的k次方=n，所以k=logn层(2为底)，所以一共需要n*logn次循环，也就是本算法 时间复杂度。当然这里忽略掉中间的一些常数。

看看下面的图会更清晰一些：

算法基础之四(归并排序)