算法简介

归并排序：是建立在归并操作上的一种有效的排序算法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。归并排序适用于数据量大，并且对稳定性有要求的场景。

一、算法步骤

1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2、 设定两个指针，最初位置分别为两个已经排序序列的起始位置

3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4、重复步骤3直到某一指针到达序列尾

5、 将另一序列剩下的所有元素直接复制到合并序列尾

二、代码实现(Java)

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {3, 7, 1, 2, 1, 2, 9, 5, 8};
        mergeSort(array);
        print(array);
    }

    public static void mergeSort(int[] arr) {
        if (arr==null || arr.length<2) return;
        mergeSort(arr, 0, arr.length-1);
    }


    private static void mergeSort(int[] arr, int left, int right) {
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid+1, right);
    }

    public static void merge(int[] array, int left, int mid, int right){
        int leftSize = mid - left;
        int rightSize = right- mid+1;
        //生成数组
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        //填充数据
        for(int i=left; i<mid; i++){
            leftArray[i-left] = array[i];
        }
        for(int i=mid; i<=right; i++){
            rightArray[i-mid] = array[i];
        }
        //合并
        int i=0;
        int j=0;
        int k=left;
        while (i<leftSize && j<rightSize){
            if(leftArray[i]<rightArray[j]){
                array[k]=leftArray[i];
                k++;
                i++;
            }else{
                array[k]=rightArray[j];
                k++;
                j++;
            }
        }
        //跑完了，i<leftSize，说明左边的数组长，把剩下的值拿过来
        while(i<leftSize){
            array[k]=leftArray[i];
            k++;
            i++;
        }
        //跑完了，j<rightSize，说明右边的数组长，把剩下的值拿过来
        while (j<rightSize){
            array[k]= rightArray[j];
            k++;
            j++;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] array) {
        for (int x : array) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}