Merge sort

Merger sort就是不斷的將兩個數組合併到一個，用 array做的話需要額外的 O(n) 空間來放排序後的結果

思路就是數組分一半左右各自遞迴 sort之後，再 merge起來完成 merge sort

想不通 merge 那邊可以這樣思考：假設現在左邊和右邊已經做完，那就只是要把左邊和右邊比大小然後放到額外的 array裡

public void sortIntegers2(int[] A) {
    int[] results = new int[A.length];
    mergeSort(A, 0, A.length - 1, results);
}

private void mergeSort(int[] array, int start, int end, int[] results) {

    //end of recursion
    if (start >= end) {
        return;
    }

    int left = start;
    int mid = (start + end) / 2;
    int right_head = mid + 1;

    mergeSort(array, left, mid, results);
    mergeSort(array, right_head, end, results);
    merge(array, start, mid, end, results);
}

private void merge(int[] array, int start, int mid, int end, int[] results) {

    int left = start;
    int right = mid + 1;
    int index = start;

    while (left <= mid && right <= end) {
        if (array[left] < array[right]) {
            results[index] = array[left];
            index++; 
            left++;
        } else {
            results[index] = array[right];
            index++; 
            right++;
        }
    }

    while (left <= mid) {
        results[index] = array[left];
        index++;
        left++;
    }

    while (right <= end) {
        results[index] = array[right];
        right++;
        index++;
    }

    for (int i = start; i <= end; i++) {
        array[i] = results[i];
    }
}

而最後面的

while (left <= mid && right <= end) {
    ...
}
while (left <= mid) {
    ...
}
while (right <= end) {
    ...
}

代表某一邊先挑完，再把剩下的寫入，因為前面是左右各自去做 merge sort，已經把左右都先 sort完

所以這裡某一邊先挑完後，表示比剩下那邊小的數都已經寫到 results了，再把剩下那邊寫入即可。