python进行归并排序

以下是使用Python实现归并排序的示例代码[^2]：

import sys

def merge(array, q, p, r):
    left_array = array[q:p+1]
    right_array = array[p+1:r+1]
    left_array_num = len(left_array)
    right_array_num = len(right_array)
    i, j, k = [0, 0, q]

    while i < left_array_num and j < right_array_num:
        if left_array[i] <= right_array[j]:
            array[k] = left_array[i]
            i += 1
        else:
            array[k] = right_array[j]
            j += 1
        k += 1

    while i < left_array_num:
        array[k] = left_array[i]
        i += 1
        k += 1

    while j < right_array_num:
        array[k] = right_array[j]
        j += 1
        k += 1

def merge_sort(array, q, r):
    if q < r:
        p = (q + r) // 2
        merge_sort(array, q, p)
        merge_sort(array, p+1, r)
        merge(array, q, p, r)

array = [5, 2, 8, 4, 1, 9, 6, 3, 7]
merge_sort(array, 0, len(array)-1)
print("Sorted array:", array)

这段代码使用了归并排序算法对一个数组进行排序。归并排序是一种分治算法，它将数组分成两个子数组，分别对子数组进行排序，然后将两个已排序的子数组合并成一个有序的数组。这个过程递归地进行，直到整个数组排序完成。