归并排序（Merge Sort）[编辑 | 编辑源代码]

归并排序是一种基于分治法（Divide and Conquer）的高效排序算法，由约翰·冯·诺伊曼于1945年提出。它的核心思想是将一个大的问题分解为若干个小问题，递归解决这些小问题，然后将它们的解合并起来得到最终结果。归并排序的时间复杂度为 $O (n \log n)$ ，在大多数情况下表现稳定，适用于大规模数据排序。

算法原理[编辑 | 编辑源代码]

归并排序的主要步骤如下： 1. 分解：将待排序的数组递归地分成两半，直到每个子数组只包含一个元素（此时可视为已排序）。 2. 合并：将两个已排序的子数组合并为一个有序数组，直到所有子数组合并完成。

分治法[编辑 | 编辑源代码]

归并排序采用分治法，其递归关系可以表示为： $T (n) = 2 T (\frac{n}{2}) + O (n)$ 其中：

$T (n)$ 表示对长度为 $n$ 的数组排序所需的时间。
$2 T (n / 2)$ 表示递归地对两个子数组排序。
$O (n)$ 表示合并两个子数组的时间。

算法实现[编辑 | 编辑源代码]

以下是归并排序的伪代码和具体实现（以Python为例）。

伪代码[编辑 | 编辑源代码]

function merge_sort(array):
    if length(array) <= 1:
        return array
    mid = length(array) // 2
    left = merge_sort(array[0..mid])
    right = merge_sort(array[mid..end])
    return merge(left, right)

function merge(left, right):
    result = []
    while left is not empty and right is not empty:
        if left[0] <= right[0]:
            append left[0] to result
            remove left[0] from left
        else:
            append right[0] to result
            remove right[0] from right
    append remaining elements of left to result
    append remaining elements of right to result
    return result

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):
    result = []
    i = j = 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

# 示例输入与输出
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序前:", arr)
print("排序后:", sorted_arr)

输出：

排序前: [38, 27, 43, 3, 9, 82, 10]
排序后: [3, 9, 10, 27, 38, 43, 82]

合并过程示例[编辑 | 编辑源代码]

以下是一个合并过程的示例（以数组[38, 27, 43, 3]为例）： 1. 分解为[38, 27]和[43, 3]。 2. 继续分解为[38]、[27]、[43]、[3]（均为已排序）。 3. 合并[38]和[27]得到[27, 38]。 4. 合并[43]和[3]得到[3, 43]。 5. 最后合并[27, 38]和[3, 43]得到[3, 27, 38, 43]。