归并排序

java实现如下：

package com.practice;

import java.util.Arrays;

public class MergeSort {
	/**
	 * 归并排序
	 */
	
	public static int[] sort(int[] arr, int l, int h) {
		int m = (l + h)/2;
		if(l < h) {
			sort(arr, l, m);  //左边归并
			sort(arr, m+1, h);  //右边归并
			mergeSort(arr, l, m, h);  //左右归并
		}
		return arr;
	}

	private static void mergeSort(int[] arr, int l, int m, int h) {
		int[] temp = new int[h-l+1];
		int i = l;
		int j = m+1;
		int k = 0;
		while(i<=m && j<=h) {
			if(arr[i]<arr[j])
				temp[k++] = arr[i++];
			else 
				temp[k++] = arr[j++];
		}
		while(i<=m)
			temp[k++] = arr[i++];
		while(j<=h)
			temp[k++] = arr[j++];
		for(int n=0;n<temp.length;n++)
			arr[l+n] = temp[n];
	} 
}