MargeSort-归并排序

import java.util.Arrays;

public class MergeSort {

	public static void sort(int arr[]) {
		if (arr == null || arr.length < 2) {
			return;
		}
		mergesort(arr, 0, arr.length - 1);

	}

	public static void mergesort(int[] arr, int L, int R) {
		if (R == L) {
			return;
		}
		int mid = L + ((R - L) >> 1); // (L+R)/2
		// 左半部分
		mergesort(arr, L, mid);
		// 右半部分
		mergesort(arr, mid + 1, R);
		// 合并数组
		merge(arr, L, mid, R);

	}

	public static void merge(int[] arr, int L, int mid, int R) {
		// 辅助数组
		int help[] = new int[R - L + 1];
		int i = 0;
		// 两个标记指针
		int p1 = L;
		int p2 = mid + 1;
		while (p1 <= mid && p2 <= R) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		// 一边越界的情况（一边大或者小永远不会放入辅助数组中）
		// 两种情况只会出现一次:p1或者p2指针越界

		// p2越界则p1一定未动，需要放入数组中
		while (p1 <= mid) {
			help[i++] = arr[p1++];
		}
		// p1越界则p2一定未动，需要放入数组中
		while (p2 <= R) {
			help[i++] = arr[p2++];
		}
		// 把辅助数值拷贝会原数组
		for (i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
	}

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

}