MergeSort

思想：将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 ，
一句话总结：两两合并在和其他的两两合并再合并

两两比较

Paste_Image.png
Paste_Image.png

两两比较

Paste_Image.png
Paste_Image.png
排序好的两组再进行比较
Paste_Image.png

以此类推

Java实现其思想

package sortingAlgo;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 水皮蛋
 * 思想：运用分治法思想解决排序问题。
 * 特点：stable sort、Out-place sort
 * 最坏情况运行时间：O(nlgn)
 * 最佳运行时间：O(nlgn)
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = createRandomArray();
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(mergeSort(arr, 0, arr.length - 1)));
    }

    public static int[] mergeSort(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            mergeSort(arr, low, mid);
            // 右边
            mergeSort(arr, mid + 1, high);
            // 左右归并
            merge(arr, low, mid, high);
        }
        return arr;
    }

    public static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左
        int j = mid + 1;// 右
        int k = 0;

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (arr[i] < arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = arr[j++];
        }

        // 把新数组中的数覆盖arr数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            arr[k2 + low] = temp[k2];
        }
    }

    /**
     * 使用Random类产生随机数组的对象
     * 
     * @return 随机数组
     */
    public static int[] createRandomArray() {
        Random random = new Random();
        int[] array = new int[10];
        for (int i = 0; i < 10; i++) {
            array[i] = random.nextInt(100);
        }
        return array;
    }

}