歸并排序實現(xiàn)簡單，但是應用場景你會嗎？

前言

歸并排序也是面試中問得比較多的，代碼量適中，也需要使用遞歸來實現(xiàn)，而且理解起來比快速排序要簡單，實現(xiàn)方式也較為單一，所以也廣受面試官的喜愛。

還沒有了解歸并排序原理的可以看一下上面的圖，它其實就是先把要排序的數(shù)組分為左右兩部分，左邊和右邊分別先遞歸排好序，然后再將兩個有序的數(shù)組合并為一個數(shù)組。

實現(xiàn)

這里需要注意的就是我們需要一個innerMergeSort的函數(shù)實現(xiàn)遞歸，具體可以直接看下代碼。

public static void innerMergeSort(int[] arr, int start, int end) {
    int mid = (end - start) / 2 + start;
    if(start < mid) {
        innerMergeSort(arr, start, mid);
    }
    if(mid + 1 < end) {
        innerMergeSort(arr, mid + 1, end);
    }
    int[] tmp = new int[end - start + 1];
    int index = 0, index1 = start, index2 = mid + 1;
    while(index1 <= mid && index2 <= end) {
        if(arr[index1] <= arr[index2]) {
            tmp[index++] = arr[index1++];
        } else {
            tmp[index++] = arr[index2++];
        }
    }
    while(index1 <= mid) {
        tmp[index++] = arr[index1++];
    }
    while(index2 <= end) {
        tmp[index++] = arr[index2++];
    }
    for(int i = 0; i < end - start + 1; i++) {
        arr[start + i] = tmp[i];
    }
}

public static void mergeSort(int[] arr) {
    innerMergeSort(arr, 0, arr.length - 1);
}

先找到mid，然后對start到mid和mid+1到end分別排序，最后將兩個有序數(shù)組merge。在merge的時候，需要定義一個額外空間tmp，同時定義三個指針，分別指向兩個有序數(shù)組和我們的目標數(shù)組。最后再將tmp的元素拷貝到原數(shù)組中。

應用

其實歸并排序有一個特點，它不需要一次性將數(shù)據(jù)全部加載到內存，也就是說用它的思想可以排序很大的文件。這其實也就是外部排序的思想。

所以如果有面試官問你有一個10億整數(shù)數(shù)據(jù)的文件，但是內存有限，你該怎么排序，你應該想到歸并排序。

練習題

學習完歸并排序，大家可以去做一下以下的習題：

leetcode912?排序數(shù)組

leetcode147?鏈表排序