Python 实现归并排序：时间复杂度分析及代码示例

归并排序算法详解及 Python 代码实现

归并排序是一种常用的排序算法，其时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

算法原理：

将待排序数组递归地分成两半，直到每个子数组只包含一个元素。
对两个有序子数组进行合并操作，将它们合并成一个新的有序数组。
重复步骤 2，直到所有子数组都被合并成一个完整的有序数组。

Python 代码实现：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

代码解释：

merge_sort(arr) 函数：递归地对数组 arr 进行归并排序。
merge(left, right) 函数：将两个有序数组 left 和 right 合并成一个新的有序数组。

时间复杂度分析：

归并排序的时间复杂度为 O(nlogn)。这是因为，在每次递归调用中，算法将数组分成两半，并将它们合并。这种操作需要 O(n) 的时间。递归调用深度为 log(n)，因此总的时间复杂度为 O(nlogn)。

空间复杂度分析：

归并排序的空间复杂度为 O(n)。这是因为，在 merge 函数中，需要额外的 O(n) 空间来存储合并后的数组。

性能测试：

对于输入规模 N=64，128, 256，512 等，归并排序的时间复杂度都为 O(NlogN)，空间复杂度为 O(N)。由于归并排序的时间复杂度较低，即使在数据规模较大的情况下，也可以在 3 分钟内完成排序。

总结：

归并排序是一种稳定、高效的排序算法，适用于各种数据规模的排序任务。其时间复杂度为 O(nlogn)，空间复杂度为 O(n)，在实际应用中表现出色。