歸并排序以?(N logN)最壞情形運(yùn)行時(shí)間運(yùn)行，而所使用的比較次數(shù)幾乎是最優(yōu)的鄙漏。

這個(gè)算法的基本操作是合并兩個(gè)已排序的表恃轩。

歸并排序大致分為兩種：

1. 自頂向下(遞歸)
2. 自底向上(迭代)

1. 實(shí)現(xiàn)

1.1 自頂向下遞歸排序

自頂向下的遞歸排序主要使用的是分治思想,代碼實(shí)現(xiàn)較為復(fù)雜脆侮。

1.1.1 實(shí)現(xiàn)流程

1. 分配等同于待排序大小的內(nèi)存空間瞎领。(必須且不會(huì)更少)
2. 對(duì)半分割泌辫，成兩個(gè)不同的部分。
3. 重復(fù)2步驟直至不能再分割九默。
4. 對(duì)兩部分分別排序震放。
5. 合并排序兩部分。
6. 返回上一級(jí)遞歸驼修。

1.1.2 代碼實(shí)現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int ElementType;

/* 歸并排序入口程序 */
void MergeSort(ElementType source[], int n);

/* 二分程序 */
static void MSort(ElementType source[], ElementType tmpArr[], int left, int right);

/* 排序合并程序 */
static void Merge(ElementType source[], ElementType tmpArr[], int left, int rightPos, int right);

void MergeSort(ElementType source[], int n) {
    ElementType *tmpArr;

    tmpArr = (ElementType *) malloc(n * sizeof(ElementType));
    if (tmpArr != NULL) {
        MSort(source, tmpArr, 0, n - 1);
        free(tmpArr);
    } else {
        printf("No Space for tmp array!!!");
        exit(EXIT_FAILURE);
    }
}


static void MSort(ElementType source[], ElementType tmpArr[], int left, int right) {
    int center;

    if (left < right) {
        center = (left + right) / 2;
        MSort(source, tmpArr, left, center);
        MSort(source, tmpArr, center + 1, right);
        Merge(source, tmpArr, left, center + 1, right);
    }
}

static void Merge(ElementType source[], ElementType tmpArr[], int left, int rightPos, int right) {

    int tmpLeft = left;
    int leftEnd = rightPos - 1;
    int tmpRight = rightPos;
    int Num = right - left + 1;

    while (tmpLeft <= leftEnd && tmpRight <= right) {
        if (source[tmpLeft] < source[tmpRight]) {
            tmpArr[left++] = source[tmpLeft++];
        } else {
            tmpArr[left++] = source[tmpRight++];
        }
    }

    while (tmpLeft <= leftEnd) {
        tmpArr[left++] = source[tmpLeft++];
    }

    while (tmpRight <= right) {
        tmpArr[left++] = source[tmpRight++];
    }

    /* 把排好的tmp復(fù)制回原數(shù)組,由于左標(biāo)志已經(jīng)被移動(dòng)因此用右標(biāo)志向左移動(dòng)倒敘放 */
    for (int i = 0; i < Num; ++i, right--) {
        source[right] = tmpArr[right];
    }

}

1.1.3 自頂向下縮短運(yùn)行時(shí)間的幾個(gè)Tips

1.1.3.1 對(duì)小規(guī)模數(shù)組使用插入排序

長(zhǎng)度小于15殿遂，一般可將時(shí)間縮短10%~15%。

1.1.3.2 測(cè)試數(shù)組是否已經(jīng)有序

如果a[mid]小于等于a[mid+1]乙各，我們就認(rèn)為數(shù)組已經(jīng)是有序的并跳過(guò)merge()方法墨礁。

1.1.3.3 不將元素賦值到輔助數(shù)組

部分歸并排序?qū)崿F(xiàn)中會(huì)現(xiàn)將數(shù)組復(fù)制到輔助數(shù)組排序后再?gòu)?fù)制回去(本例中沒(méi)有這么做)。這種操作是可以避免的耳峦。

1.2 自低向上歸并排序

自底向上的思想是恩静，先兩兩合并最小的，再四四合并相對(duì)小的妇萄，如此這般蜕企，直到我們將整個(gè)數(shù)組歸并到一起。

1.2.1 實(shí)現(xiàn)流程

1. 將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作冠句，形成 floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素
2. 將上述序列再次歸并懦底，形成 floor(n/4)個(gè)序列唇牧，每個(gè)序列包含四個(gè)元素
3. 重復(fù)步驟2，直到所有元素排序完畢

1.2.2 算法圖解

插入排序

插入排序

1.2.3 代碼實(shí)現(xiàn)

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 + 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++];
        }
        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);
}

2. 時(shí)間復(fù)雜度

最差時(shí)間復(fù)雜度 ?( nlog n )
最優(yōu)時(shí)間復(fù)雜度 ?( n )
平均時(shí)間復(fù)雜度 ?( nlog n )

最差空間復(fù)雜度 ?( n )