相信大家都知道合并排序的基本思想.
在这里我要想请问大家的是自然合并排序,当然总的思想是一样的.
自然合并排序:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段,直至整个数组已排好序.

所指的是二路归并排序嘛...思想就是你叙述的这样啊

自然合并排序和二路归并排序只是第一次的划分不一样
如果是{8,7,6,5,4,3,2,1}
自然合并 {8},{7},{6},{5},{4},{3},{2},{1}
二路归并 {7,8},{5,6},{4,3},{2,1}
可见，自然合并对数列中已基本有序的有利
如：
{1,2,3,4,5,6,7,8} 只分成一个
{5,6,7,8,1,2,3,4} 只分成二个
不过，在随机数列中，自然合并和二路归并第一次划分的个数应该差不了多少