归并排序（Merge Sort） O(nlog(n))

介绍

归并排序是利用归并的思想实现排序，采用经典的分治（divide-and-conquer）策略，先把大问题拆成小问题然后递归，合并各个小问题的结果。

mergeSort.png

算法描述

• 申请空间，使其大小为待排序序列的长度
• 将序列递归拆分成两部分,直到不能拆分后进行归并
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  重复步骤4直到某一指针超出序列尾

稳定性

稳定，拆分的过程不会改变相同元素相对位置

动图展示

mergeSort.gif

代码实现

public class MergeSort {
    public static void main(String[] args) {
        int[] arrays = new int[]{27, 6, 27, 42, 23, 15, 38, 50, 35, 14, 40, 28, 29};
        mergeSort(arrays);
    }

    private static void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];
        sort(arr, temp, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int[] temp, int min, int max) {
        if (min < max) {
            int mid = Math.floorDiv(min + max, 2);
            sort(arr, temp, min, mid);
            sort(arr, temp, mid + 1, max);
            merge(arr, temp, min, mid, max);
            print(arr);
        }
    }

    private static void merge(int[] arr, int[] temp, int min, int mid, int max) {
        int left = min;
        int right = mid + 1;
        int t = 0;
        while (left <= mid && right <= max) {
            if (arr[left] <= arr[right]) {
                temp[t++] = arr[left++];
            } else {
                temp[t++] = arr[right++];
            }
        }
        while (left <= mid) {
            temp[t++] = arr[left++];
        }
        while (right <= max) {
            temp[t++] = arr[right++];
        }
        System.arraycopy(temp, 0, arr, min, t);
    }

    private static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}