编写Python函数实现归并排序算法

归并排序（Merge Sort）是一种基于分治策略的排序算法，其基本思想是将原始数组分成较小的数组，直到每个小数组只有一个元素，然后将这些小数组合并为较大的数组，最终得到一个有序的数组。

实现归并排序算法的关键是实现合并（Merge）操作。在合并操作中，我们需要创建一个临时数组，将两个已排序的子数组按照顺序合并到临时数组中，最后将临时数组的元素复制回原始数组。

下面是Python代码实现归并排序算法的一个例子：

def merge_sort(arr):
    # 递归终止条件：当数组长度为1时，即认为数组已经有序
    if len(arr) <= 1:
        return arr
    
    # 将数组分成两个子数组
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]

    # 递归地对两个子数组进行归并排序，并合并结果
    left_arr = merge_sort(left_arr)
    right_arr = merge_sort(right_arr)
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    # 创建一个临时数组来存储合并后的结果
    merged_arr = []
    
    # 初始化左右子数组的下标
    left_index = 0
    right_index = 0
    
    # 依次比较左右子数组的元素，将较小的元素添加到合并数组中
    while left_index < len(left_arr) and right_index < len(right_arr):
        if left_arr[left_index] <= right_arr[right_index]:
            merged_arr.append(left_arr[left_index])
            left_index += 1
        else:
            merged_arr.append(right_arr[right_index])
            right_index += 1
    
    # 将剩余的元素添加到合并数组中
    merged_arr.extend(left_arr[left_index:])
    merged_arr.extend(right_arr[right_index:])
    
    return merged_arr

这段代码中的merge_sort函数实现了归并排序算法。它首先将数组分成两个子数组，然后递归地对每个子数组进行归并排序。最后，它调用merge函数将两个已排序的子数组合并为一个有序的数组。

merge函数实现了合并操作。它创建一个临时数组来存储合并后的结果。然后，它初始化左右子数组的下标，依次比较左右子数组的元素，并将较小的元素添加到合并数组中。最后，将剩余的元素添加到合并数组中。

归并排序的时间复杂度是O(nlogn)，其中n是数组的长度。归并排序是一种稳定的排序算法，适用于大规模数据的排序。

使用归并排序算法对一个数组进行排序的示例如下：

arr = [4, 2, 5, 1, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)  # 输出 [1, 2, 3, 4, 5]

以上就是使用Python实现归并排序算法的示例代码。通过递归地将问题分解为更小的子问题，并使用适当的合并策略，归并排序算法能够高效地解决排序问题。