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

自然合并排序:对于初始给定的数组,通常存在多个长度大于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}).继续合并相邻排好序的子数组段,直至整个数组已排好序.