Python实现归并排序：算法复杂度及代码示例

归并排序是一种高效、稳定的排序算法，其基于分治思想，将待排序序列逐步分解成更小的子序列，直到每个子序列只有一个元素，然后再将排好序的子序列合并成更大的排序序列。

算法复杂度

时间复杂度： O(nlogn)，无论最好、最坏还是平均情况下，归并排序的时间复杂度均为 O(nlogn)。* 空间复杂度： O(n)，归并排序需要额外的空间来存储临时数组，因此空间复杂度为 O(n)。

Python代码实现

以下是归并排序的Python代码实现：pythondef 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): 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

运行时间测试

以下代码演示了对不同规模的随机整数数组进行归并排序，并输出排序时间：pythonimport randomimport time

for n in [64, 128, 256, 512, 1024, 2048, 4096]: arr = [random.randint(1, 10000) for _ in range(n)]

start_time = time.time()    sorted_arr = merge_sort(arr)    end_time = time.time()

print(f'n = {n}, time = {end_time - start_time:.4f}s')

注意： 实际运行时间会受硬件配置和测试数据的影响。