视频字幕
归并排序是计算机科学中最重要的排序算法之一。它采用分治策略，将复杂问题分解为简单的子问题。首先将数组不断分解，直到每个子数组只有一个元素，然后再将这些有序的子数组合并成更大的有序数组。这种方法保证了稳定的时间复杂度。
分解过程是归并排序的第一步。我们从原始数组开始，不断将其分成两半。第一次分解得到两个子数组，然后继续分解每个子数组，直到每个子数组只包含一个元素。这个过程形成了一个二叉树结构，树的深度为log n，这也是归并排序时间复杂度中log n因子的来源。
合并过程是归并排序的核心。我们有两个已排序的子数组，需要将它们合并成一个更大的有序数组。首先比较两个数组的第一个元素，3小于4，所以将3放入结果数组。然后比较8和4，4较小，放入结果数组。接着比较8和5，5较小。最后将剩余的8放入结果数组。这样就完成了一次合并操作。
现在让我们看完整的归并排序过程。从原始数组开始，经过分解后，我们从最底层开始合并。第一层将相邻的单个元素两两合并，得到四个长度为2的有序数组。第二层将相邻的两个数组合并，得到两个长度为4的有序数组。最后一层将这两个数组合并，得到完全排序的数组。整个过程体现了分治算法的精髓。
归并排序具有优秀的算法特性。它的时间复杂度在所有情况下都是O(n log n)，这使得它在处理大数据集时表现稳定。递推关系T(n) = 2T(n/2) + O(n)表明每层的合并成本为O(n)，总共有log n层，因此总时间复杂度为O(n log n)。虽然空间复杂度为O(n)，但它是稳定排序，适用于需要保持相等元素相对顺序的场合。