我们知道归并排序是将一个无序的数组两两划分，最终划分成每个组内有序的子元素，组后再将若干个组内有序的元素合并成一个完整有序的数组。这个思路可以使用递归和非递归算法来实现，我在此主要讲自然合并排序
自然合并排序当然也是合并排序，所谓的自然只不过就是指：所划分的子数组不在是两两划分，而是每一个子数组都是已经有序的，且每个子数组的长度不在确定。这就是自然合并排序与合并排序的区别。 如数组
{1，5， 3， 6， 7， 2，4}将此数组可以自然划分为三个有序的子数组
{1，5} {3，6，7} {2,4}由于自然划分的不确定性，所以此算法无法由递归实现，具体代码如下：
#include <stdio.h> // 记录初始自然排好序的子数组段的起始下标及个数 int getIndex(int *list, int *index, int n) { int count = 0; index[count++] = 0; for (int i = 0; i < n-1; i++) { if (list[i+1] < list[i]) { index[count++] = i+1; } } return count; } //将一个数组内的两个子数组合并 // left是第一个有序子数组段的起始下标 // middle是第一个有序子数组段的末尾下标 // right是第二个有序子数组段的末尾下标 void mergeSublist(int *list_1, int *list_2, int left, int middle, int right) { int i = left; int j = middle+1; // j为第二个的起始下标 int k = left; while (i <= middle && j <= right) { // 每次取两段中较小的一个 if (list_1[i] <= list_1[j]) { list_2[k++] = list_1[i++]; }else { list_2[k++] = list_1[j++]; } } // 合并两段中的剩余部分 while (i <= middle) { list_2[k++] = list_1[i++]; } while (j <= right) { list_2[k++] = list_1[j++]; } } //合并过程函数 //将组内有序的数组合并，具体合并由Merge()实现 /* 每合次s增加，就合并一段子数组 每个子数组的起始位置记录在t数组中 index[i] 表示要合并第一个子数组的起始元素在原数组的下标 即每次合并的left index[i+s]-1 表示要合并的第一个子数组的最后一个元素在原数组的下标 即每次合并的middle index[i+2*s]-1 表示每次要合并的第二个子数组的最后一个元素 即每次合并的right */ void mergePass(int *list_1, int *list_2, int *index, int s, int count, int n) { int i = 0; //当前数组内至少有三个子数组 while (i < count - 2*s) { mergeSublist(list_1, list_2, index[i], index[i+s]-1, index[i+2*s]-1); i = i + 2*s; } //当前数组内含有两个子数组段 if (i + s < count) { mergeSublist(list_1, list_2, index[i], index[i+s]-1, n-1); } //当前数组内只有一个子数组段 else if (i < count) { for (int j = index[i]; j <= n -1; j++) { list_2[j] = list_1[j]; } } } void mergeSort(int *list_1, int *index, int count, int n) { int list_2[n]; int s = 1; while (s < count) { mergePass(list_1, list_2, index, s, count, n); s += s; mergePass(list_2, list_1, index, s, count, n); s += s; } } int main(void) { int list[100], index[100]; int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &list[i]); } int count = getIndex(list, index, n); /*//输出标记数组 for (int i = 0; i < count; i++) { printf("%d ", index[i]); } printf("\n"); */ mergeSort(list, index, count, n); for (int i = 0; i < n; i++) { printf("%d ", list[i]); } return 0; }测试结果 输入：
7 1 5 3 6 7 2 4输出：
1 2 3 4 5 6 7如果代码运行出现错误，请在评论区回复作者，不胜感激！
