利用Python编写归并排序算法

归并排序是一种分治算法，它将待排序的序列不断划分为较小的子序列，直到子序列只包含一个元素，然后通过将相邻的子序列进行合并，最终得到一个有序的序列。

归并排序的核心思想是将待排序的序列不断划分为两个子序列，分别对这两个子序列进行排序，然后再将排序后的子序列合并得到一个有序的序列。具体步骤如下：

1. 划分：将待排序的序列一分为二，分别得到左右两个子序列。

2. 递归排序：对左右两个子序列分别进行递归排序。

3. 合并：将排序后的子序列合并为一个有序的序列。

下面是使用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):
    result = []
    i, j = 0, 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.extend(left[i:])
    result.extend(right[j:])
    
    return result

以上代码中，merge_sort函数是递归地对序列进行归并排序的函数，它将序列一分为二，并分别对左右子序列进行递归排序。而merge函数是将排序后的左右子序列进行合并的函数，它比较左右子序列的元素，并按照从小到大的顺序将它们添加到结果序列中。

最后，我们可以通过调用merge_sort函数对一个待排序的序列进行归并排序。比如，对一个包含多个整数的列表进行排序：

arr = [5, 2, 8, 4, 1, 9, 6, 3, 7]
sorted_arr = merge_sort(arr)
print(sorted_arr)

以上代码的输出结果为：[1, 2, 3, 4, 5, 6, 7, 8, 9]，即将序列按照从小到大的顺序进行了排序。

归并排序的时间复杂度是O(nlogn)，其中n是待排序序列的长度。归并排序是一种稳定的排序算法，适用于待排序序列长度较大的情况。