第37讲：什么是归并排序（上）

问题 1： 什么是归并排序？
回答： 归并排序是一种高效的排序算法，它通过将数组分成较小的部分，分别排序后再合并起来，最终实现整个数组的有序排列。

问题 2： 归并排序和快速排序有什么区别？
回答： 归并排序和快速排序都是高效的排序算法，但归并排序是一种稳定的排序算法，而快速排序是不稳定的。归并排序的时间复杂度始终为O(n log n)，而快速排序在最坏情况下可能达到O(n²)。

问题 3： 归并排序的时间复杂度是多少？
回答： 归并排序的时间复杂度为O(n log n)，其中n是数组的长度。

问题 4： 归并排序的空间复杂度是多少？
回答： 归并排序的空间复杂度为O(n)，因为它需要额外的空间来存储合并过程中的临时数组。

问题 5： 归并排序适用于哪些场景？
回答： 归并排序适用于需要稳定排序的场景，尤其是在处理链表或外部排序时，归并排序表现尤为出色。

问题 6： 归并排序的基本步骤是什么？
回答： 归并排序的基本步骤包括：1. 将数组分成两半；2. 递归地对每一半进行排序；3. 将排序后的两半合并成一个有序数组。

问题 7： 归并排序的合并过程是如何实现的？
回答： 合并过程通过比较两个有序数组的元素，依次将较小的元素放入临时数组中，直到所有元素都被合并为一个有序数组。

问题 8： 归并排序的稳定性是什么意思？
回答： 归并排序的稳定性是指在排序过程中，相等元素的相对位置不会改变，这对于某些需要保持元素顺序的应用场景非常重要。

问题 9： 归并排序在处理大数据集时有什么优势？
回答： 归并排序在处理大数据集时，由于其时间复杂度始终为O(n log n)，因此在数据量较大时仍能保持较高的效率，尤其适合外部排序。

问题 10： 归并排序的递归实现和非递归实现有什么区别？
回答： 归并排序的递归实现是通过递归调用将数组不断分割，而非递归实现则是通过迭代的方式模拟递归过程。非递归实现通常使用循环和栈来替代递归调用，避免了递归带来的额外开销。