归并排序是一种高效、分治策略的排序算法,通过递归地将数组分为两半,分别排序后再合并,以实现整体排序。
归并排序(Merge Sort)是一种高效且稳定的“分治”排序算法。其核心策略可以概括为“先递归拆分,再有序合并”。它会持续地将一个大数组对半切分,直到每个部分都只剩一个元素(此时天然有序)。接着,再反向地将这些相邻的有序部分两两配对,按大小顺序合并成一个更长的有序数组,不断重复此过程,直到最终还原成一个完整的有序序列。
归并排序的性能极其稳定,无论原始序列是好是坏,时间复杂度都保持在卓越的 O(nlogn)。与快速排序的“就地交换”不同,它通过“有序合并”实现排序,这一特性也保证了其排序的稳定性(相同元素的原始相对顺序在排序后不会改变),但通常需要额外的存储空间来辅助合并操作。

...