歸并排序主要采取分治的思想，也可以說是遞歸的思想。

在學(xué)習(xí)鏈表的時候，我們會遇到 如何將兩個有序表合并成一個有序表的問題，歸并排序就是類似地利用了這一個操作。

這里以 2-路歸 并為例：

提示：2-路歸并是最簡單也是最常見的一種歸并排序方式

想要排一個序列，可以將這個序列從中間分為左右兩個序列。

當(dāng)左右兩個序列分別被排列成一個有序序列后，再合并為一個有序序列。

而想要排列左右兩個有序序列，則又可以將這兩個序列依次分為兩個序列，再進行排序后再合并。

注意：歸并排序并不是全部分好后合并，而是一邊先分好再合并，再另一邊分好再合并

不斷的重復(fù)操作后，可以將排序轉(zhuǎn)化為如何按序合并的問題。

圖示（來源于網(wǎng)絡(luò)）：

歸并排序的思想轉(zhuǎn)化為操作就是遞歸合并了（這里是我常用的寫法）:

#includeusing namespace std;
const int N = 1e6+10;	//序列大長度
int temp[N];	// 歸并排序需要用到一個臨時存儲數(shù)據(jù)的序列
int a[N];	//待排序序列

void Msort(int arr[],int left,int right){	// 歸并排序
    //遞歸邊界  歸并排序觸碰到遞歸邊界后，才開始真正的排序操作。
    if(left>=right) return;
    //折中拆分
    int mid=(left+right)/2;      //或?qū)懗?mid = left+right>>1
    Msort(arr,left,mid);               //左邊
    Msort(arr,mid+1,right);         //右邊
    //有序合并	
    int k=left,i=left,j=mid+1;	//k輔助處理數(shù)據(jù) i相當(dāng)于左指針 j相當(dāng)于右指針
    while(i<=mid&&j<=right){	//從小到大排序
        if(arr[i]

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧