python排序算法-（5）归并排序

import random

# 归并函数
def merge(arr, l, m, r):
    # 创建两个零数组
    n1 = m - l + 1
    n2 = r - m
    L = [0] * (n1)
    R = [0] * (n2)

    # 复制数组元素
    for i in range(0, n1):
        L[i] = arr[l + i]
    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

    # 合并子数组
    i = 0  # 第一个子数组的初始索引
    j = 0  # 第二个子数组的初始索引
    k = l  # 合并后的子数组的初始索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 复制L剩余的元素（如果有）
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 复制R剩余的元素（如果有）
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

# 归并排序函数
def mergeSort(arr, l, r):
    if l < r:
        m = (l+r)//2
        # 对左右两个子数组进行递归排序
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        # 合并左右两个有序子数组
        merge(arr, l, m, r)

# 测试
array=random.sample(range(0, 100), 50)
print("原始数组为:")
print(array)

size = len(array)
mergeSort(array,0,size-1)

print('归并排序后的数组为:')
print(array)