归并排序算法

归并排序是一种经典的排序算法，其基本思想是将待排序的序列分成若干个子序列，然后将每个子序列排序，最后合并成一个有序序列。具体实现过程如下：

1. 将待排序序列分成若干个子序列，每个子序列包含一个元素。
2. 将相邻的子序列两两合并，得到若干个长度为2的有序子序列。
3. 将相邻的有序子序列两两合并，得到若干个长度为4的有序子序列。
4. 重复上述步骤，直到得到一个长度为n的有序序列为止。

归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。它是一种稳定的排序算法，适用于各种数据类型和数据量较大的情况。

下面是归并排序的 Python 代码实现：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    result = []
    i, j = 0, 0
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

在上述代码中，merge_sort 函数是递归实现的归并排序，merge 函数用于合并两个有序子序列。