双向自然合并排序算法

Bilateral nature-merge sorting algorithm

双向自然合并排序是根据欲排序数据局部不是升序就是降序的自然有序特点,先线性扫描出自然有序的子数组段,再进行合并排序.扫描时的有序数段长度越长,段数越少,对应合并树的层数就会越少,算法的效率越高.

Local data is always ascending or descending, so we scan all data to find ascending and descending segments, then merge every segment from down to up. The longer the ascending segments or descending segments are, the smaller the number of segments is and the grater the efficiency of the algorithm is.