2-路归并排序算法详解及示例

"归并排序是一种排序算法，它通过分治法将数据分成较小的子序列，然后将这些子序列合并成一个大的有序序列。在2-路归并排序中，算法将序列拆分为两半，分别对每半进行排序，然后合并两个已排序的半部分。核心算法`Merge`负责将两个有序数组合并成一个。如果数组未完全填充，剩余元素会被复制到目标数组。整个排序过程通过递归的`MSort`函数执行，直到每个子序列仅包含一个元素，然后再逐层合并。" 归并排序是一种高效的排序算法，基于“分而治之”的策略。它首先将待排序的序列分割成两半，对每一半分别进行排序，然后将两个已经排序的子序列合并成一个整体有序序列。这个过程不断递归进行，直到每个子序列只有一个元素，此时的子序列自然有序。之后，这些单元素序列两两合并，形成双元素有序序列，再继续合并，直到最终得到完整的有序序列。 在给定的代码中，`Merge`函数是归并排序的核心，它接收三个参数：`SR[]`是原始数组，`TR[]`是临时数组，`i`, `m`, `n`分别表示数组的起始、中间和结束索引。该函数的主要任务是合并两个已排序的子数组`SR[i..m]`和`SR[m+1..n]`到目标数组`TR[i..n]`。通过一个循环，比较`SR[i]`和`SR[j]`的键值，将较小的元素放入`TR`，并更新对应索引。如果某一半序列还有剩余元素，则将其余元素复制到目标数组。 `MSort`函数是归并排序的递归部分，它将序列`SR[s..t]`归并排序到`TR1[s..t]`。首先检查是否序列只包含一个元素，如果是，直接复制到目标数组。否则，将序列平分为两半，并递归调用`MSort`对每一半进行排序，最后调用`Merge`将两个已排序的子序列合并。 2-路归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)，其中n是待排序元素的数量。虽然它需要额外的存储空间，但其稳定性（相同元素的相对顺序在排序后保持不变）和优秀的平均性能使其成为解决大规模数据排序问题的有效方法。此外，归并排序不仅限于内部排序，也可以应用于外部排序，处理大量无法一次性加载到内存的数据。