标签：java

    所谓合并排序，就是将两个部分的数组合并在一起，但是有个前提就是两个数组本身就是已经排好序的。它包括两个问题，一个合并，一是排序。
    基本思想就是将一个数组从中间分为两个部分，先对左边排序，再对右边排序，最后将两边再合并出来即可了。采用递归手段，我们可以递归的对左边排序，对右边排序，最后合并。

    由于要将两个子数组合并为一个新的数组，因此需要一个额外的空间来存储这些数据信息。因此，我们需要建立一个与原数组大小相同的数组，用于合并过程。合并完了之后，再将额外空间中的数据copy回原来的空间，即完成整个排序工作。

    现在来看程序逻辑，程序逻辑已按照先分面两个部分，再分别递归排序，然后再合并的思路，具体代码如下：

	/** 归并排序，ints为要排序的数组 */
	public static void guibingSort(int[] ints) {
		int[] temp = new int[ints.length];
		guibingSort(ints, temp, 0, ints.length - 1);
	}

	/** 归并排序,ints为要进行排序的数组，temp为临时数组,start为排序起点,end为排序终点,排序范围为[start,end] */
	private static void guibingSort(int[] ints, int[] temp, int start, int end) {
		if(start >= end)
			return;
		int middle = (start + end) / 2;//中间点
		int left = start;//左边起点
		int right = middle + 1;//右边起点
		guibingSort(ints, temp, left, middle);//左边排序
		guibingSort(ints, temp, right, end);//右边排序
		//将两边的数组进行合并
		int i;
		for(i = start;  left <=  middle && right <= end;) {
			if(ints[left] > ints[right])
				temp[i++] = ints[right++];
			else
				temp[i++] = ints[left++];
		}
		//将左边没有合并完的添加到temp中
		while(left <= middle)
			temp[i++] = ints[left++];
		//将右边没有合并完的添加到temp中
		while(right <= end)
			temp[i++] = ints[right++];
		//最后将这些数字转回到ints
		System.arraycopy(temp, start, ints, start, end - start + 1);
	}

    代码的主要部分在于合并，合并的思路即对两个数组从开头分别比较，将比较小的那个加入到额外数组中去，这个过程一直持续到其中有一个数组完成，最后将剩下数组的剩余部分全部copy至额外数组即可（因为，两个数组是排好序的，在copy过程中可以保证排序的正确性）。

    合并排序与快速排序的最大一个区别在于，合并排序需要使用额外的空间，而且数据在排序过程中需要进行不断的进行数据之间的复制，并且用于比较的次数较小；而快速排序则需要对数据进行不断的移动，而不需要进行数据复制，却需要进行大量的比较操作。因为在java中，所有的数据都是按引用进行排序，数据移动和复制都是走引用，因此，花费较小，并且进行对象间的比较花费较大，因此在进行对象比较时，都是使用的合并排序算法。而其它语言，如c++，则是使用快速排序来进行排序，他们依赖的即是对象的大小比较。