Python实现归并排序

2744557306

下面是使用Python实现归并排序的示例代码：

```python
def merge_sort(arr):
    # 递归终止条件：当数组长度小于等于 1 时，直接返回该数组
    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):
    merged = []
    i, j = 0, 0

    # 比较两个子数组的元素，将较小的元素依次放入 merged 数组中
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    # 将剩余的元素依次放入 merged 数组中
    while i < len(left):
        merged.append(left[i])
        i += 1
    while j < len(right):
        merged.append(right[j])
        j += 1

    return merged

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

在上面的代码中，`merge_sort` 函数实现了归并排序的逻辑，使用递归的方式将数组划分为子数组并进行排序，然后再将排序好的子数组进行合并。`merge` 函数实现了合并两个已排序的子数组的逻辑，依次将较小的元素放入新的数组中。最后，我们通过调用 `merge_sort` 函数并传入待排序的数组进行测试，打印排序后的结果。运行代码后，输出的结果即为归并排序后的数组。