归并排序（Merge Sort）

1. 什么是归并排序

归并排序是建设在归并操作上的一种无效，稳固的排序算法，该算法是采纳分治法的一个十分典型的利用。将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2. 算法步骤

1. 申请空间，使其大小为两个曾经排序序列之和，该空间用来寄存合并后的序列；
2. 设定两个指针，最后地位别离为两个曾经排序序列的起始地位；
3. 比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间，并挪动指针到下一地位；
4. 反复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素间接复制到合并序列尾。

3. 动图演示

4. 代码实现

public static void main(String[] args) {
    // 初始化数组
    int[] arr = {5,3,1,4,2,7,8,6,10,9};
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
    System.out.println(Arrays.toString(arr));
}

public static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = (left + right) / 2;
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);
        merge(arr, left, mid, right, temp);
    }
}

public static void merge(int[] arr, int l, int mid, int r, int[] temp) {
    int i = 0;
    int left = l;
    int right = mid + 1;
    while (left <= mid && right <= r) {if (arr[left] < arr[right]) {temp[i++] = arr[left++];
        } else {temp[i++] = arr[right++];
        }
    }

    while (left <= mid) {temp[i++] = arr[left++];
    }

    while (right <= r) {temp[i++] = arr[right++];
    }

    for (int k = 0; k < i; k++) {arr[l + k] = temp[k];
    }
}

5. 输入后果

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]