python 实现归并排序算法

下面是一个用Python实现的归并排序算法示例。归并排序是一种分而治之的算法，它将数组分成两半，对每半部分递归地进行归并排序，然后将结果合并在一起。

def merge_sort(arr):
    if len(arr) > 1:
        # 找到中间位置，将数组分成两半
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        # 递归地对每半部分进行归并排序
        merge_sort(L)
        merge_sort(R)

        # 合并两个有序数组
        i = j = k = 0

        # 复制数据到临时数组temp，以便按顺序合并L[]和R[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 检查是否还有剩余的元素
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 示例
arr = [12, 11, 13, 5, 6, 7]
print("原始数组:", arr)
merge_sort(arr)
print("排序后的数组:", arr)

这段代码首先检查数组的长度是否大于1，如果是，则找到中间位置将数组分成两部分，并对每部分递归地进行归并排序。然后，它使用三个索引`i`、`j`和`k`来合并两个已排序的部分。最后，它检查并合并任何剩余的元素。注意，归并排序在原地修改数组，不需要额外的存储空间（除了递归调用栈）。