自然合併排序

自然合併排序是合併排序算法的一種改進.

自然合併排序:對於初始給定的數組,通常存在多個長度大於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}).繼續合併相鄰排好序的子數組段,直至整個數組已排好序.