/**
 * Created by Avalon on 2017/1/21.
 */
public class MergeSort {

    /**
     * 主调用程序
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        if (arr != null) {
            merge(arr, 0, arr.length - 1);
        }
    }

    /**
     * 递归调用
     * @param arr
     * @param first
     * @param last
     */
    private static void merge(int[] arr, int first, int last) {
        if (first >= last) {
            return;
        }
        int mid = (last + first) / 2;
        merge(arr, first, mid);
        merge(arr, mid + 1, last);

        mergeTwoArr(arr, first, mid, last);
    }

    /**
     * 将两个有序的数组合并
     * @param arr
     * @param first
     * @param mid
     * @param last
     */
    private static void mergeTwoArr(int[] arr, int first, int mid, int last) {
        int temp[] = new int[arr.length];

        int left = first;
        int right = mid + 1;

        int step = 0;
        while (left <= mid || right <= last) {
            int leftNum = Integer.MAX_VALUE, rightNum = Integer.MAX_VALUE;
            if (left <= mid) {
                leftNum = arr[left];
            }
            if (right <= last) {
                rightNum = arr[right];
            }

            // 比较两边大小
            if (leftNum <= rightNum) {
                temp[step] = leftNum;
                left++;
            } else {
                temp[step] = rightNum;
                right ++;
            }
            step ++;
        }

        // 赋值
        for (int i = first, j = 0; i <= last; i++) {
            arr[i] = temp[j++];
        }
    }
}