非递归归并排序算法实现与输出示例

归并排序是一种高效的排序算法，它采用分治策略将复杂问题分解成更小的子问题来解决。在给定的题目中，8645归并排序是非递归版本，适用于SCAU（石河子大学）的编程练习，要求使用C++（G++或GCC）语言编写。该算法的主要目标是将一串整数按照升序排列，并在每次合并过程中输出排序结果。 归并排序的过程分为以下几个步骤： 1. **划分阶段**（Divide）：首先，将原始数组分割成两半，直到每个子数组只包含一个元素。这里使用的是一个固定的初始长度（`length=1`），然后每次翻倍（`length=length*2`），直到长度达到数组长度的一半。 2. **合并阶段**（Combine）：对于每个子数组，将它们视为已排序的序列，通过`MergeWork`函数将这两个子数组合并成一个更大的已排序数组。这个函数接收三个参数：混合数组的总长度（`mixlength`）、左子数组的起始位置（`Lstart`）和右子数组的起始位置（`Rstart`）。通过比较左右子数组中的元素，将较小的放入临时数组`temp`，并更新对应的指针。当其中一个子数组遍历完，将另一个剩余部分直接复制到临时数组。 3. **遍历和输出**：合并后的有序序列存储在`temp`数组中，通过`Travels`函数将其输出到控制台，每趟排序后显示一次结果。输出格式要求数据之间用空格分隔。 4. **递归终止条件**：当数组长度`n`小于或等于1时，无需进一步分割，直接认为已排序，此时停止递归。 在给定的代码片段中，`MergeSort`函数的主体包含了整个过程的循环，即不断划分、合并和输出，直到整个数组排好序。这个非递归版本相比于传统的递归实现，更加直观且易于理解和调试，尤其适合教学和初学者实践。 输入样例中，有10个整数作为待排序序列，输出展示了排序过程中的每一步结果，最终会得到完全排序后的序列。这个题目有助于巩固学生对归并排序的理解，锻炼他们的编程技能以及处理大数组的能力。