归并排序算法实现及展示

"该资源提供了一种非递归实现归并排序的方法，通过函数Merge进行合并操作，并在每轮排序后输出当前结果。程序中包括了主函数main、归并函数Merge、打印数组函数print以及非递归归并排序函数MSort。" 归并排序是一种高效的排序算法，它采用了分治法的思想。在这个非递归实现中，我们首先将数组分成大小为2的子数组，然后不断合并相邻的子数组，直到整个数组有序。这个过程通过MSort函数完成，它接收原始数组S、临时数组L和数组长度length作为参数。 MSort函数内部首先复制原始数组到临时数组，然后通过一个while循环逐步增大子数组的大小（每次乘以2），在每个循环里，遍历所有可能的子数组对，使用Merge函数进行合并。Merge函数接受四个参数：源数组SR、目标数组TR、起始索引i、中间索引m和结束索引n，它将两个已排序的子数组合并成一个大的有序数组。 Merge函数的核心在于两个嵌套的for循环，第一个循环用于合并两个子数组，第二个循环用于处理剩余的部分，如果其中一个子数组已经全部合并到目标数组，则将另一个子数组剩余部分直接复制到目标数组。 在每一轮合并操作后，使用print函数打印出当前的排序状态，以便观察排序过程。最后，当子数组大小达到整个数组长度的一半时，最后一次调用Merge函数将剩下的部分合并，完成整个排序。 在main函数中，用户输入待排序的关键字个数n，然后依次输入这些关键字，MSort函数对输入的数组进行归并排序，并输出排序过程中每一趟的结果。 这种非递归的归并排序避免了递归带来的栈空间开销，适用于大数据量的排序，且由于归并排序的稳定性，使得相同元素的相对顺序在排序后不会改变，这在某些应用场景中非常重要。