归并排序

归并排序是一种经典的排序算法，它是基于分治思想的。该算法的基本思想是：将待排序的序列不断划分成若干个子序列，每个子序列排序后再合并，最终得到一个有序的序列。

归并排序的具体步骤如下：

1. 将待排序序列划分成若干个子序列，直到每个子序列只有一个元素。
2. 将相邻的两个子序列进行合并，得到一个更大的有序序列。
3. 重复步骤2，直到整个序列有序为止。

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

def merge_sort(arr):
    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 = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result += left
    result += right
    return result

归并排序的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。归并排序是稳定的排序算法，适合处理大规模数据的排序问题。