小白学算法归并排序

　　归并排序算法是在分治算法基础上设计出来的一种排序算法，它可以对指定序列完成升序（由小到大）或降序（由大到小）排序，对应的时间复杂度为O(n*logn)。
　　归并排序算法实现排序的思路是：将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素； 所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。 递归实现： // 递归方法实现
　　public static void mergeSort(int[] arr) {
　　if (arr == null || arr.length < 2) {
　　return;
　　}
　　// 递归排序
　　process(arr, 0, arr.length - 1);
　　}
　　// 把arr[L..R]排有序
　　// O(N * logN)
　　public static void process(int[] arr, int L, int R) {
　　// 边界判断
　　if (L == R) { // base case
　　return;
　　}
　　// 获取当前分段中间索引
　　int mid = L + ((R - L) >> 1);
　　// 对左半部分进行排序
　　process(arr, L, mid);
　　// 对右半部分进行排序
　　process(arr, mid + 1, R);
　　// 合并
　　merge(arr, L, mid, R);
　　}
　　public static void merge(int[] arr, int L, int M, int R) {
　　// 辅助数组
　　int[] help = new int[R - L + 1];
　　int i = 0;
　　int p1 = L;
　　int p2 = M + 1;
　　while (p1 <= M && p2 <= R) {
　　help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
　　}
　　// 要么p1越界了，要么p2越界了
　　while (p1 <= M) {
　　help[i++] = arr[p1++];
　　}
　　while (p2 <= R) {
　　help[i++] = arr[p2++];
　　}
　　// 排序后的数组赋值给原数组
　　for (i = 0; i < help.length; i++) {
　　arr[L + i] = help[i];
　　}
　　}
　　非递归实现，迭代：// 非递归方法实现
　　public static void mergeSort(int[] arr) {
　　if (arr == null || arr.length < 2) {
　　return;
　　}
　　int N = arr.length;
　　// 初始步长
　　int mergeSize = 1;
　　while (mergeSize < N) { // log N
　　// 当前左组的，第一个位置
　　int L = 0;
　　while (L < N) {
　　if (mergeSize >= N - L) {
　　break;
　　}
　　int M = L + mergeSize - 1;
　　// 计算右边界
　　int R = M + Math.min(mergeSize, N - M - 1);
　　// 合并
　　merge(arr, L, M, R);
　　L = R + 1;
　　}
　　// 防止溢出
　　if (mergeSize > N / 2) {
　　break;
　　}
　　mergeSize <<= 1;
　　}
　　}
　　辅助验证对数器：
　　public static int[] generateRandomArray(int maxSize, int maxValue) {
　　int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
　　for (int i = 0; i < arr.length; i++) {
　　arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
　　}
　　return arr;
　　}