先举个例子看一下自然合并排序和合并排序的区别：

可以看出自然合并排序在最初时就有已经排好序的子数组，再利用合并排序的原理对于已经排好序的子数组进行两两合并。
一个解释：

合并排序 :
是将两个（或两个以上）有序表合并成一个新的有序表
自然合并排序：
就是在合并排序时，建立子数组段，通过数组已排序的（自然排序,不重新排序）子数组段。

问题：

自然合并排序算法是对合并排序算法的一种改进。设a[0:n-1]是无序数组，用一次对数组a的扫描可以找出其中自然排好序的子数组，然后将相邻的排好序的子数组段两两合并，继续合并相邻排好序的子数组段，直至将整个数组排好序。

思路：
自然合并排序是合并排序的改进，应用的原理是：对于一个给定的数组a，通常会有长度大于1的有序子序列，我们称之为自然有序子序列.自然归并排序是找出给定数组中的自然子序列，将其开始的下标位置保存起来，然后对两个子序列之间进行插入排序形成一个大的有序子序列，直到整个数组排序完成。
大概思路我们首先定义一个全局变量n，控制数组的长度。在给定数组长度的前提，考虑数组子序列数最遭的情况就是整个数组对我们要求的序列刚好成一个反序列，即子序列的个数就是数组元素的个数。所以定义两个长度为n的数组 a、b，一个保存数组元素a[i]，另一个保存自然子序列的起始下标值b[i]。
下面的代码一共是1个主函数4个子函数，主函数首先调用GetIndex()函数，获得自然分组后每个子串的起始坐标，以及自然分组的个数，再在GetIndex()中调用MergeSort()函数将子序列划分，再在MergeSort()中调用MergePass()函数，将相邻子数组进行合并，再在MergePass()函数中调用Merge()函数合并对应索引的数组。

上代码：

#include<iostream>
using namespace std;
#include <stdlib.h>

// 这个函数记录自然分组后每个子串的起始坐标
void GetIndex(int a[], int t[], int n, int &m){
 
    
    /*a为输入数组，t为自然分组后每个分组的起始值组成的数组，
	n为数组长度 ，m自然分组个数*/ 
    int j = 0;
    t[j++] = 0; 
    for(int i = 0; i < n-1; i++) {
        if(a[i+1] < a[i]) {
            t[j++] = i+1;
        }
    }
    m = j;      // m为自然分组的个数
}

//(3)
// 合并c[l:m]和c[m+1:r]到d[l:r]
void Merge(int *c,int *d,int l,int m,int r)

{
	/*
	
	*/
	int i=l,j=m+1,k=l;//左右子数组的当前处理索引，合并后的索引
	while(i<=m && j<=r) {
		if(c[i]<=c[j])  d[k++]=c[i++];
		else d[k++]=c[j++];
	}
	if(i>m)//左子数组全部并入数组d，同时右子数组还有值未并入数组d
		for(int q=j; q<=r; q++)
			d[k++]=c[q];
	else
		for(int q=i; q<=m; q++)
			d[k++]=c[q];
}

 //(2)
 // 将x中长度为s的相邻子数组合并，结果存入y中
void MergePass(int *x,int *y,int *t,int s,int n,int cnt)
{
/*
x为输入的数组，y为长度为n的数组 
t是分组后子数组的索引的数组，cnt为自然分组个数 
*/ 


// n: 数组元素数量

	int i=0;  //子数组起始位置
	while(i+2*s<=cnt) {   //s为子数组长度 ，cnt为自然分组个数 
		int r=((i+2*s)<cnt) ?  t[i+2*s]:n; 
		//
		Merge(x,y,t[i],t[i+s]-1,r-1);
		i+=2*s;
	}
	if(i+s<cnt) { //剩下的元素少于2s
		//剩下的元素多于s
		Merge(x,y,t[i],t[i+s]-1,n-1);
	} 
	else {
		//剩下的元素不多于s
		for(int j=t[i]; j<n; j++)
			y[j]=x[j];
	}
 
}


 //(1):相邻两个数组合并 
void MergeSort(int *a,int *t,int n,int cnt)
{
	/*a为原数组 
	t为自然分组后每个分组的起始值组成的数组，
	n为数组长度 ，cnt自然分组个数
	*/
	int b[n];
	int s=1;//子数组长度
	while(s<cnt) {
		
		//将长度为s的相邻子数组两两合并（合并成的新数组内部有序）
		//并将这样的结果保存到数组b
		MergePass(a,b,t,s,n,cnt);
		
		//子数组的长度增加一倍
		s+=s;
		//同样使相邻的两个（内部有序）子数组合并成一个长度为"2s"的内部有序新数组保存到数组a 
		MergePass(b,a,t,s,n,cnt);
		s+=s;
	}
}

int main()
{
	int n;
	cout<<"输入数组元素个数：";
	cin>>n;
	int a[n];
	int t[n]; 
	cout<<"输入"<<n<<"个元素：";
	for(int i=0;i<n;i++){
		cin>>a[i];
	} 
	//Print(a,n);
	int cnt;        // 记录自然分组个数
    GetIndex(a, t, n, cnt);
	MergeSort(a,t,n,cnt);
	for(int i=0;i<n;i++) cout<<a[i]<<" "; 
	return 0;
}

既然是详解自然合并排序，那就一步一步讲解算法： (‾◡◝)
学习自然合并排序，首先我们要先知道：

自然合并排序和合并排序的区别：

合并排序 :
是将两个（或两个以上）有序表合并成一个新的有序表
自然合并排序：
就是在合并排序时，建立子数组段，通过数组已排序的（自然排序,不重新排序）子数组段。

下面通过步骤讲解自然合并排序到底是怎样操作的：( ﹁ ﹁ ) ~→

自然合并排序步骤：

简单的说，自然分组排序就是：
(1)先检查数组内部有没有已经排好序的子数组段；
将数组划分成一个一个有序的子数组段，
子数组段个数最大为数组n　　(´ｰ∀ｰ`)

即没有已经排好序的，比如要求升序数组，数组是{9,8,7,6,5}，那么子数组段就为{9}、{8}、{7}、{6}、{5}

最小为1　　(´ｰ∀ｰ`)

即已经按照要求有序了，比如{5,6,7,8,9}。

再来一个不极端的例子：

比如：{4,8,3,7,1,5,6,2}，自然排好序的子数组段{4,8}、{3,7}、{1,5,6}、{2}；

(2)分好子数组段后，从第一个开始将相邻的两个子数组段合并成一个数组。然后重新分段，再合并，直到子数组段变为1

比如子数组段{4,8}、{3,7}、{1,5,6}、{2}
第一次合并：{3,4,7,8}、{1,2,5,6}
第二次合并：{1,2,3,4,5,6,7,8}
结束

好了。这就是大概步骤了，是不是觉得思想很简单，但是实现起来还是没有头绪　　(￣_,￣ )
没关系，我们通过代码一点一点讲解

自然合并排序算法讲解：

（一）首先是第一步骤，先将原数组a进行分段，
我们需要新开辟一个数组，用这个数组来记录下每个子数组段的首位置，这样就可以达到分割数组的目的，给数组起名为temp：

        for(i=0;i<n-1;i++) //分段
        {
            if(a[i]>a[i+1])
            {
                temp[j++]=i+1;
                k++;//k是总共有多少段
            }
        }
        temp[j]=n;

因为循环里我是将i+1作为下标放进去，所以退出条件为n-1
用k来表示总共有多少段，作为一会儿判断子段数为1时合并结束的条件
最后多加一个n的目的是作为最后一段结束的位置，后面函数需要用，可以先往下看

（二）用一个while循环，循环退出条件为k>1，也就是子数组段为1的时候退出
i表示temp下标位置，j表示合并次数，应该小于段数k除以2，比如有6段就需要合并3次，３段合并1次，最后一段空出（我之前用i<k-2来表示结束条件，发现奇偶段会出现问题）

        int f=k;
        while(k>1)
        {
            for(j=0,i=0;j<k/2;j++,i+=2) //两个相邻的进行合并
            {
                hebing(temp[i],temp[i+1],temp[i+2]);
                f--;
            }
            newtemp(temp,k);
            k=f;
        }
        

f的作用是暂代一下新的k值，因为在重新标记子数组段函数里需要知道原来有多少段，所以k值在没有经过这个函数前不能减小。
for循环里合并子数组段函数传的参数是：第一个子数组段首位置、第二个子数组段首位置、第二个子数组段末位置（也就是第三个子数组段首位置减1，由于我后面函数是统一将下一个子数组段首位置设为前一个子数组段末位置，所以在这里没有减）

（三）合并子数组段函数
合并两个子数组的思想很简单，开辟一个新数组x，x的大小为最后一个数组末位置减去第一个数组首位置
然后将两个数组大小进行比较，按顺序插入
最后判断一下哪个数组有剩余，加入新数组里
再将新数组里已经排好的值赋给原来数组a。

    void hebing(int begin,int mid ,int end ) //合并子数组段函数
    {
        int i=0,j;
        int x[end-begin];
        int l1=begin,l2=mid;  //标记一下
        while(l1!=mid && l2!=end)//合并入新数组x
        {
            if(b[l1]<b[l2])
            {
                x[i++]=b[l1++];
            }
            else
            {
                x[i++]=b[l2++];
            }
        }
        if(l1==mid) //如果l1排完了，该l2
        {
            while(l2!=end)
            {
                x[i++]=b[l2++];
            }
        }
        if(l2==end) //如果l2排完了，该l1
        {
            while(l1!=mid)
            {
                x[i++]=b[l1++];
            }
        }

        for(i=0,j=begin;i<end-begin;i++)  //排好序的新数组值赋给原数组
        {
            b[j++]=x[i];
        }
    }

之前的给temp多赋值一个n，在这里就是作为最后一个子数组段的末位置传入的

（四）重新标记子数组段函数
这个函数思想也很简单，因为是相邻的两两合并，所以直接去掉temp里除了0外的偶数下标值
但是因为每次i是加2的，所以容易跳过最后的单数的值，所以在最后判断一下，如果没有给加上，要不然最后一个子数组段没有末位置会出错

    void newtemp(int *temp,int f)  //重新标记子数组段函数
    {
        int i,j=0;
        for(i=0;i<=f;i+=2)    //赋新值，每次加2，跳过已经被合并的数组下标值
        {
            temp[j++]=temp[i];
        }
        if(temp[j-1]!=n)
        {
            temp[j]=n;
        }
    }

好了，主要核心代码和思想就解释完了，
完整代码：（我写的感觉不太好，大家尽量自己改进啊）　( -’`-; )

#include<iostream>
#include<vector>
using namespace std;
class solution
{
private:
    int *b;int n,k=1;
public:
    int* ziran(int *a,int s)
    {
        b=a;n=s;
        int temp[n];
        temp[0]=0;
        int i,j=1;
        for(i=0;i<n-1;i++) //分段
        {
            if(a[i]>a[i+1])
            {
                temp[j++]=i+1;
                k++;//k是总共有多少段
            }
        }
        temp[j]=n;
        for(i=0;i<k;i++)//输出子段
        {
            cout<<temp[i];
        }
        cout<<endl;
        int f=k;
        while(k>1)
        {
            for(j=0,i=0;j<k/2;j++,i+=2) //两个相邻的进行合并
            {
                hebing(temp[i],temp[i+1],temp[i+2]);
                f--;
            }
            newtemp(temp,k);
            k=f;
        }
        return a;
    }
    
    void newtemp(int *temp,int f)
    {
        int i,j=0;
        for(i=0;i<=f;i+=2)
        {
            temp[j++]=temp[i];
        }
        if(temp[j-1]!=n)
        {
            temp[j]=n;
        }
    }

    void hebing(int begin,int mid ,int end )
    {
        int i=0,j;
        int x[end-begin];
        int l1=begin,l2=mid;
        while(l1!=mid && l2!=end)//合并入新数组x
        {
            if(b[l1]<b[l2])
            {
                x[i++]=b[l1++];
            }
            else
            {
                x[i++]=b[l2++];
            }
        }
        if(l1==mid) //如果l1排完了，该l2
        {
            while(l2!=end)
            {
                x[i++]=b[l2++];
            }
        }
        if(l2==end) //如果l2排完了，该l1
        {
            while(l1!=mid)
            {
                x[i++]=b[l1++];
            }
        }

        for(i=0,j=begin;i<end-begin;i++)
        {
            b[j++]=x[i];
        }
    }

};

int main()
{
    int n,i;
    cout<<"数组个数：";
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int *b;
    solution k;
    b=k.ziran(a,n);
    for(i=0;i<n;i++)
    {
        cout<<b[i];
    }
}

后记

可能我指针学的不太好，所以这个题在写的时候有很多段错误的bug，而且不停徘徊在值和数组下标里很晕，太菜了．．．　　┭┮﹏┭┮
自然合并排序在已知数组已经有很多有序的子段时，效率还是非常高的
开始写这个的时候很懵
然后csdn搜了半天，发现就是简单的几句话带过思想，然后直接是完整代码，感觉这样慢慢去研究代码又没有注释啥的很烦 (＞﹏＜)
所以想写一篇比较详细的，之后也会更一些碰见比较烦的算法题。
︿(￣︶￣)︿

一、合并排序（归并排序）概念 / 思想

定义：（引用自"百度百科"）

• 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
• 合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
• 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。

算法步骤：（引用自"菜鸟教程"）

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

示例图：

二、分治算法实现

1. 设计递归方程

1. 我们需要将序列拆分，将当前区间一分为二，即求中间点；

2. 递归地对两个子区间 L[left…mid] 和 R[mid+1…right] 进行归并排序（即再次执行第一步）；

3. 当拆分后的子序列只含有一个元素时，将已排序的两个子区间 L[left…mid] 和 R[mid+1…right] 合并为一个有序的区间[left…right]。

2. 编写程序代码

// 合并排序
#include<iostream>

using namespace std;

void mergeSort(int array[], int left, int right);
void merge(int array[], int left, int mid, int right);

int main()
{
	// 待排序数组，也可进行改写，获取键盘输入进行排序
	int array[] = { 10,5,8,6,3,9,4,1,2,7 };
	int len = sizeof(array) / sizeof(int); // 数组长度
	
	mergeSort(array, 0, len-1);
	cout << "合并排序：";
	for (int i = 0;i < len;i++)
		cout << array[i] << " ";
	cout << endl;
	
	return 0;
}

void mergeSort(int array[], int left, int right)
{
	// 当子序列就只有一个元素的时候结束递归调用
	if (left == right)
		return;
	else {
		// 分治
		// 判断中间位置，进行拆分
		int mid = (left + right) / 2;
		mergeSort(array, left, mid);
		mergeSort(array, mid + 1, right);
		// 合并
		merge(array, left, mid, right);
	}
}

void merge(int array[], int left, int mid, int right)
{
	// 声明一个指针，指向临时数组，临时存放排序后的元素
	int* tempArray = new int[right - left + 1];

	int left_1 = left;		// 指向 左待排序区域 第一个元素
	int left_2 = mid + 1;	// 指向 右待排序区域 第一个元素
	int k = 0;				// 指向 临时数组 第一个元素

	// 顺序选取两个待排序区的较小元素，存储到tempArr数组中
	while (left_1 <= mid && left_2 <= right) {
		// 将较小的元素存入tempArr数组中，并将指针递增
		if (array[left_1] <= array[left_2])
			tempArray[k++] = array[left_1++];
		else
			tempArray[k++] = array[left_2++];
	}
	// 若比较完之后，有序区仍有剩余元素，则直接复制到tempArray数组中
	while (left_1 <= mid)
		tempArray[k++] = array[left_1++];
	while (left_2 <= right)
		tempArray[k++] = array[left_2++];

	// 将临时数组中排序后的元素取出
	for (int i = left, j = 0;i <= right;i++,j++)
		array[i] = tempArray[j];

	// 删除指针
	delete[] tempArray;
}

3. 运行结果展示

4. 程序改进

程序只是举例排序{ 10,5,8,6,3,9,4,1,2,7 }，
可以使用cin获取用户输入替代此数组，对用户输入的数据进行排序。

三、自然合并排序

1. 概念 / 基本思想

• 自然合并排序是合并排序算法的一种改进；

• 对于初始给定的数组，通常存在多个长度大于1的已排好序的子数组段。因此用一次线性扫描就可以找出所有这些排好序的子数组段，然后将相邻的排好序的子数组段两两合并。

• 注：通常情况下, 按此方式进行合并排序所需的合并次数较少。

• 举个栗子：

  • 数组a中元素为{2, 5, 8, 3, 6, 10, 4, 9}；
  • 用一次对数组a的线性扫描，找出自然排好序的子数组段：{2, 5, 8}，{3, 6}，{10}，{4, 9}；
  • 然后将相邻的排好序的子数组段两两合并：{2, 3, 5, 6, 8}，{4, 9, 10}；
  • 继续合并直至整个数组排好序{2, 3, 4, 5, 6, 8, 9, 10}。

2. 编写程序代码

// 待更新。。。

3. 运行结果展示

运行截图（待更新。。。）

三、友情链接~

• 其它一些常见算法请参阅此链接~

最后，非常欢迎大家来讨论指正哦！