合併排序和歸併排序

排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分爲內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是歸併排序算法：

歸併排序（Merge sort）是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

作爲一種典型的分而治之思想的算法應用，歸併排序的實現由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；自下而上的迭代；

在《數據結構與算法 JavaScript 描述》中，作者給出了自下而上的迭代方法。但是對於遞歸法，作者卻認爲：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中這種方式不太可行，因爲這個算法的遞歸深度對它來講太深了。

說實話，我不太理解這句話。意思是 JavaScript 編譯器內存太小，遞歸太深容易造成內存溢出嗎？還望有大神能夠指教。

和選擇排序一樣，歸併排序的性能不受輸入數據的影響，但表現比選擇排序好的多，因爲始終都是 O(nlogn) 的時間複雜度。代價是需要額外的內存空間。

2. 算法步驟

申請空間，使其大小爲兩個已經排序序列之和，該空間用來存放合併後的序列；

設定兩個指針，最初位置分別爲兩個已經排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置；

重複步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接複製到合併序列尾。

3. 動圖演示

---

代碼實現

JavaScript

實例

function mergeSort(arr) {  // 採用自上而下的遞歸方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

Python

實例

def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

Go

實例

func mergeSort(arr []int) []int {
        length := len(arr)
        if length < 2 {
                return arr
        }
        middle := length / 2
        left := arr[0:middle]
        right := arr[middle:]
        return merge(mergeSort(left), mergeSort(right))
}

func merge(left []int, right []int) []int {
        var result []int
        for len(left) != 0 && len(right) != 0 {
                if left[0] <= right[0] {
                        result = append(result, left[0])
                        left = left[1:]
                } else {
                        result = append(result, right[0])
                        right = right[1:]
                }
        }

        for len(left) != 0 {
                result = append(result, left[0])
                left = left[1:]
        }

        for len(right) != 0 {
                result = append(result, right[0])
                right = right[1:]
        }

        return result
}

Java

實例

public class MergeSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 對 arr 進行拷貝，不改變參數內容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }
        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    protected int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0;
        while (left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result[i++] = left[0];
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }

        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }

        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }

        return result;
    }

}

PHP

實例

function mergeSort($arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right)
{
    $result = [];

    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }

    while (count($left))
        $result[] = array_shift($left);

    while (count($right))
        $result[] = array_shift($right);

    return $result;
}

C

實例

int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

遞歸版：

實例

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 1);
}

C++

迭代版：

實例

template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

遞歸版：

實例

void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = (front + end) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

C#

實例

public static List<int> sort(List<int> lst) {
    if (lst.Count <= 1)
        return lst;
    int mid = lst.Count / 2;
    List<int> left = new List<int>();  // 定義左側List
    List<int> right = new List<int>(); // 定義右側List
    // 以下兩個循環把 lst 分為左右兩個 List
    for (int i = 0; i < mid; i++)
        left.Add(lst[i]);
    for (int j = mid; j < lst.Count; j++)
        right.Add(lst[j]);
    left = sort(left);
    right = sort(right);
    return merge(left, right);
}
/// <summary>
/// 合併兩個已經排好序的List
/// </summary>
/// <param name="left">左側List</param>
/// <param name="right">右側List</param>
/// <returns></returns>
static List<int> merge(List<int> left, List<int> right) {
    List<int> temp = new List<int>();
    while (left.Count > 0 && right.Count > 0) {
        if (left[0] <= right[0]) {
            temp.Add(left[0]);
            left.RemoveAt(0);
        } else {
            temp.Add(right[0]);
            right.RemoveAt(0);
        }
    }
    if (left.Count > 0) {
        for (int i = 0; i < left.Count; i++)
            temp.Add(left[i]);
    }
    if (right.Count > 0) {
        for (int i = 0; i < right.Count; i++)
            temp.Add(right[i]);
    }
    return temp;
}

Ruby

實例

def merge list
  return list if list.size < 2

  pivot = list.size / 2

  # Merge
  lambda { |left, right|
    final = []
    until left.empty? or right.empty?
      final << if left.first < right.first; left.shift else right.shift end
    end
    final + left + right
  }.call merge(list[0...pivot]), merge(list[pivot..-1])
end

參考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/5.mergeSort.md

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

以下是熱心網友對歸併排序算法的補充，僅供參考：

熱心網友提供的補充1：

分而治之

可以看到這種結構很像一棵完全二叉樹，本文的歸併排序我們採用遞歸去實現（也可採用迭代的方式去實現）。分階段可以理解爲就是遞歸拆分子序列的過程，遞歸深度爲log2n。

合併相鄰有序子序列

再來看看治階段，我們需要將兩個已經有序的子序列合併成一個有序序列，比如上圖中的最後一次合併，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合併爲最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟。

import java.util.Arrays;/** * Created by chengxiao on 2016/12/8. */public class MergeSort {    public static void main(String []args){        int []arr = {9,8,7,6,5,4,3,2,1};        sort(arr);        System.out.println(Arrays.toString(arr));    }    public static void sort(int []arr){        int []temp = new int[arr.length];//在排序前，先建好一個長度等於原數組長度的臨時數組，避免遞歸中頻繁開闢空間        sort(arr,0,arr.length-1,temp);    }    private static void sort(int[] arr,int left,int right,int []temp){        if(left<right){            int mid = (left+right)/2;            sort(arr,left,mid,temp);//左邊歸併排序，使得左子序列有序            sort(arr,mid+1,right,temp);//右邊歸併排序，使得右子序列有序            merge(arr,left,mid,right,temp);//將兩個有序子數組合並操作        }    }    private static void merge(int[] arr,int left,int mid,int right,int[] temp){        int i = left;//左序列指針        int j = mid+1;//右序列指針        int t = 0;//臨時數組指針        while (i<=mid && j<=right){            if(arr[i]<=arr[j]){                temp[t++] = arr[i++];            }else {                temp[t++] = arr[j++];            }        }        while(i<=mid){//將左邊剩餘元素填充進temp中            temp[t++] = arr[i++];        }        while(j<=right){//將右序列剩餘元素填充進temp中            temp[t++] = arr[j++];        }        t = 0;        //將temp中的元素全部拷貝到原數組中        while(left <= right){            arr[left++] = temp[t++];        }    }}

以上爲歸併排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等排序算法各有優缺點，用一張圖概括：

關於時間複雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序；

O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數。 希爾排序

線性階 (O(n)) 排序 基數排序，此外還有桶、箱排序。

關於穩定性

穩定的排序算法：冒泡排序、插入排序、歸併排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k："桶"的個數

In-place：佔用常數內存，不佔用額外內存

Out-place：佔用額外內存

穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同