归并排序python代码实现

归并排序是一种高效的排序算法，采用分治法的一个典型应用。它将一个数组分成两半，分别对它们进行排序，然后将结果合并起来。归并排序在合并过程中会将两个有序数组合并成一个更大的有序数组。

以下是归并排序的一个Python实现示例：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 将数组分成左右两部分，并对它们进行排序
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 合并两个有序数组
    return merge(left, right)

def merge(left, right):
    merged_arr = []
    left_index, right_index = 0, 0
    
    # 遍历两个数组，按顺序将元素添加到新的数组中
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged_arr.append(left[left_index])
            left_index += 1
        else:
            merged_arr.append(right[right_index])
            right_index += 1
    
    # 如果左边或右边数组还有剩余的元素，直接将它们添加到新数组中
    merged_arr.extend(left[left_index:])
    merged_arr.extend(right[right_index:])
    
    return merged_arr

# 测试
if __name__ == "__main__":
    test_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    sorted_array = merge_sort(test_array)
    print(sorted_array)

这段代码首先定义了`merge_sort`函数，它通过递归的方式将数组分成更小的部分，并对每一部分调用`merge_sort`。当数组不能继续分割时（长度小于等于1），返回数组本身。然后通过`merge`函数将两个有序数组合并成一个更大的有序数组。