python merge合并排序算法

python merge合并排序算法

引言

合并排序（Merge Sort）是一种比较简单而且高效的排序算法。它采用分治法（Divide and Conquer）的思想，将原始数组不断地分割成更小的子数组，直到每个子数组只有一个元素，然后再将这些单个元素按照顺序合并成有序数组。

合并排序的时间复杂度为O(nlogn)，对于大规模数据集合排序，合并排序通常表现出色。

算法实现

下面我们来看一下合并排序的Python实现代码：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    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

# 测试代码
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr)

运行上面的代码，你将会看到输出为：

[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

算法分析

时间复杂度

在最坏、最好和平均情况下，合并排序都需要O(nlogn)的时间复杂度。这是由于在每一层递归中，数组都会被分成两半，然后将这两半子数组合并成一个有序数组，从而需要O(n)的时间复杂度。而总共需要logn层递归。

空间复杂度

合并排序的空间复杂度主要来自于递归调用的栈空间和临时数组的空间。在每次递归调用中，都会将数组分成两个子数组，因此需要O(logn)的栈空间。而合并操作需要一个临时数组来存储已排序的结果，所以需要O(n)的空间。因此，合并排序的总空间复杂度为O(n+logn)。

稳定性

合并排序是一种稳定的排序算法。当两个元素大小相同时，合并排序不会改变它们的相对位置，所以合并排序是稳定的。

总结

合并排序是一种高效、稳定的排序算法，在处理大规模数据集合时表现出色。通过分治法的思想，将问题分解成更小的子问题，再将子问题的解合并起来，从而解决原始问题。合并排序的时间复杂度为O(nlogn)，空间复杂度为O(n+logn)。在实际应用中，合并排序是一个非常实用的排序算法。