排序之归并排序（MergeSort()）

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = {9,8,7,6,5,4,3,2,1};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}

	private static void sort(int[] arr) {
		// TODO Auto-generated method stub
		int[] temp = new int[arr.length];
		sort(arr, 0, arr.length - 1, temp);
	}

	private static void sort(int[] arr, int left, int right, int[] temp) {
		// TODO Auto-generated method stub
		if(left < right) {
			int mid = (left + right)/2;
			sort(arr, left, mid, temp);
			sort(arr, mid + 1,right, temp);
			merge(arr, left, right, temp);
		}
	}
private static void merge(int[] arr, int left, int right, int[] temp) {
		// TODO Auto-generated method stub
		int mid = (left + right)/2;
		int i = left;
		int j = mid + 1;
		int k = 0;
		while(i <= mid && j <= right) {
			if(arr[i] < arr[j])
				temp[k++] = arr[i++];
			else
				temp[k++] = arr[j++];
		}
		while(i <= mid)
			temp[k++] = arr[i++];
		while(j <= mid)
			temp[k++] = arr[j++];
		int t = 0;
		while(left <= right)
			arr[left++] = temp[t++];
			
	}

}

运行结果：
[1, 2, 3, 4, 5, 6, 7, 8, 9]