import java.util.*;

public class MergeSort {

    public static void mergeSort(int[] array) {
        int[] workArray = new int[array.length];
        Sort(array, workArray, 0, array.length - 1);
    }

    private static void Sort(int[] array, int[] workArray, int start, int end) {
        if (start >= end) return;
			
        //避免溢位 start + end 可能超出去
		int mid = start + (end - start)/2;

        Sort(array, workArray, start, mid);
        Sort(array, workArray, mid+1, end);
        Merge(array, workArray, start, mid, mid+1, end);
    }

    private static void Merge(int[] array, int[] workArray, int leftStart, int leftEnd, int rightStart, int rightEnd) {
        int leftPtr = leftStart, rightPtr = rightStart, index = leftStart;
        while (leftPtr <= leftEnd || rightPtr <= rightEnd) {
            if (leftPtr <= leftEnd && rightPtr <= rightEnd) {
				
				//最後一排
                if (array[rightPtr] < array[leftPtr])
                    workArray[index] = array[rightPtr++];
                else
                    workArray[index] = array[leftPtr++];
				
            } else if (leftPtr <= leftEnd){
				// 左邊排序
				workArray[index] = array[leftPtr++];
			}else{
				// 右邊排序
				workArray[index] = array[rightPtr++];
			}   
            ++index;
        }
        for (int i = leftStart; i < index; i++)
            array[i] = workArray[i];
    }

    public static void main(String[] args) {
        int[] data = new int[10];
        for (int i = 0; i < data.length; i++) {
            data[i] = (int) (Math.random() * 100);
        }

        System.out.println("before: " + Arrays.toString(data));
        mergeSort(data);
        System.out.println("after: " + Arrays.toString(data));
    }
}