java 简单 数组 自然合并排序

题目：对所给元素存储于数组中或链表中（选择一种情形），写出自然合并排序算法

结果演示：

基本思想：

自然排序是在合并排序的基础上修改而成。

①合并排序

给出一个n个元素无序的整数数组， 将其一分为2，则一个子集为n/2，再将子集划分为2，不断划分直到只有一个元素。

如 9  8  6  7  3  4  5  2 1，划分为{9},{8},{6},{7},{3},{4},{5},{2},{1}

在相邻的两两合并排序，如合并一次为{8,9}，{6,7}，{3,4}，{5,2}，{1}

不断重复合并排序直至全部被合并成一个有序数组。

②自然合并排序

（1）与合并排序的主要不同为划分子集方法。自然合并排序根据非按自然排列（一般指递增）的子段划分，只有后面的数比前面小，则划开。

如 9  8  6  7  3  4  5  2 1，划分为{9},{8},{6，7},{3࿰