整理定义

复述展开

归并排序，又称为合并排序，采用分治法进行序列排序，是一种稳定性的排序算法，算法复杂度为O(nlogn)。

代码演示：

def merge_sort(nums):
    """
    归并排序 (Merge Sort)
    归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。
    将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2 - 路归并。

    和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

    算法步骤
    归并排序算法是一个递归过程，边界条件为当输入序列仅有一个元素时，直接返回，具体过程如下：
    1.如果输入内只有一个元素，则直接返回，否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
    2.分别对这两个子序列进行归并排序，使子序列变为有序状态；
    3.设定两个指针，分别指向两个已经排序子序列的起始位置；
    4.比较两个指针所指向的元素，选择相对小的元素放入到合并空间（用于存放排序结果），并移动指针到下一位置；
    5.重复步骤 3 ~4 直到某一指针达到序列尾；
    6.将另一序列剩下的所有元素直接复制到合并序列尾。

    算法分析
    稳定性：稳定
    时间复杂度 ：最佳：O(nlogn)， 最差：O(nlogn)， 平均：O(nlogn)
    空间复杂度 ：O(n)
    """

    def merge(nums_a: List[int], nums_b: List[int]) -> List[int]:
        ans = []
        i = 0
        j = 0
        while i < len(nums_a) and j < len(nums_b):
            if nums_a[i] <= nums_b[j]:
                ans.append(nums_a[i])
                i += 1
            else:
                ans.append(nums_b[j])
                j += 1
        ans.extend(nums_a[i:])
        ans.extend(nums_b[j:])
        return ans

    length = len(nums)
    if length <= 1:
        return nums
    middle = length // 2
    left = merge_sort(nums[:middle])
    right = merge_sort(nums[middle:])
    return merge(left, right)

动图演示：

理解体会

归并排序是一种分治算法，其基本思想是将两个或两个以上的有序表合并成一个新的有序表。具体步骤如下：

1. 分解：将当前区间一分为二，递归地对它们进行分解，直到分解到一个元素为止。

2. 合并：将分解出的数列合并，合并过程为：将两个有序数列合并成一个有序数列，我们称之为二路归并。

特点：

1. 稳定性：归并排序是一种稳定的排序方法，即相等的元素的顺序不会改变。

2. 非原地排序：归并排序需要额外的空间来存储元素，因此空间复杂度为O(n)。

优点：

1. 对于大规模数据的排序，归并排序是非常有效的。因为其时间复杂度为O(nlogn)，这在所有的时间复杂度为O(nlogn)的排序算法中，性能表现最稳定。

2. 归并排序适合对链表进行排序，因为链表的节点分布可以看作是随机的，归并排序只需要重新排列链表节点的指针即可。

缺点：

1. 需要额外的存储空间，空间复杂度为O(n)。

2. 对于小规模数据，插入排序等简单排序算法可能更有效。

使用场景：

1. 处理大规模数据：归并排序适合处理大规模数据，因为其时间复杂度为O(nlogn)。

2. 链表排序：归并排序是链表排序的最佳选择，因为它不需要随机访问元素。

对比同类算法：

1. 快速排序：快速排序在最坏情况下的时间复杂度为O(n^2)，而归并排序在所有情况下的时间复杂度都是O(nlogn)。但是，快速排序是原地排序，不需要额外的存储空间，而归并排序需要。

2. 堆排序：堆排序和归并排序的时间复杂度都是O(nlogn)，但堆排序是原地排序算法，而归并排序不是。然而，堆排序不是稳定的排序算法，而归并排序是。

总结： 归并排序是一种高效、稳定、但非原地的排序算法。它对处理大规模数据和链表排序非常有效。但是，由于其需要额外的存储空间，对于存储空间有限或者数据规模较小的情况，可能不如其他排序算法有效。