归并排序算法及实现

归并排序是分治法的一种典型运用，时间复杂度和快排及堆排序一样，是O(nlongn)。是一个不断将两个有序数组合并为一个有序数组的过程，合并两个有序数组的时间复杂度为O(n)。

归并排序的基本思路：将数组二分为两部分A,B，如果这两部分有序，那么合并后就得到有序数组，为了保证A,B有序，我们继续将A,B分别二分，直至得到的两个部分只包含一个元素，则认为这两部分有序，然后再合并两个相邻的小组。这样先递归的分，再合并数列就完成了归并排序。

归并排序的实现如下：

public class MergeSort {
	/*
	 * 合并两个有序数组，并将结果放回原数组中。
	 */
	private void mergeArray(int[] a, int start, int mid, int end, int[] arr) {
		int i = start, j = mid + 1;
		int k = 0;
		while(i <= mid && j <= end) {
			if(a[i] <= a[j]) {
				arr[k++] = a[i++];
			}
			else {
				arr[k++] = a[j++];
			}
		}
		while(i <= mid) {
			arr[k++] = a[i++];
		}
		while(j <= end) {
			arr[k++] = a[j++];
		}
		
		for(int t = 0; t < k; t ++) {
			a[start+t] = arr[t];
		}
	}
	/*
	 * 递归地将数组分为两部分，直至两部分只包含一个元素。
	 */
	private void mergeSort(int[] a, int start, int end, int[] arr) {
		if(start < end) {
			int mid = (start + end) >> 1;
			mergeSort(a, start, mid, arr);
			mergeSort(a, mid+1, end, arr);
			mergeArray(a, start, mid, end, arr);
		}
	}
	
	public static void main(String[] args) {
		int[] a = {3,4,1,5,2};
		int n = a.length;
		int[] arr = new int[n];
		MergeSort m = new MergeSort();
		m.mergeSort(a, 0, n-1, arr);
		boolean flag = true;
		for(int i = 0; i < 0; i ++) {
			if(flag) flag = false;
			else
				System.out.print(" ");
			System.out.print(a[i]);
		}
		System.out.println();
	}

}