归并排序算法时间复杂度：理解分治策略，提升算法效率

# 1. 归并排序算法简介**

归并排序是一种基于分治策略的高效排序算法，它将一个无序数组划分为较小的有序子数组，然后合并这些子数组形成一个有序的最终数组。归并排序的优点在于它的时间复杂度为 O(n log n)，无论输入数组的初始状态如何，它都能保证稳定的排序结果。

# 2. 分治策略与归并排序

### 2.1 分治策略的原理

分治策略是一种经典的算法设计范式，它将一个复杂的问题分解成一系列更小的子问题，然后递归地解决这些子问题，最终合并子问题的解得到原问题的解。分治策略的优点在于它可以将复杂问题简化为更易于管理的小问题，从而提高算法的效率。

### 2.2 归并排序的流程

归并排序是一种基于分治策略的排序算法，它将一个无序的数组分解成更小的子数组，对子数组进行排序，然后合并排序后的子数组得到最终的排序结果。归并排序的流程如下：

1. **分解：**将数组分成两个大小相等或接近相等的子数组。
2. **征服：**递归地对每个子数组进行归并排序。
3. **合并：**将排序后的子数组合并成一个有序的数组。

**代码块 2.1：Python 实现归并排序**

def merge_sort(arr):
    """
    归并排序算法

    参数：
        arr: 待排序数组

    返回：
        排序后的数组
    """

    # 递归终止条件：数组长度为 1 时返回
    if len(arr) <= 1:
        return arr

    # 分解：将数组分成两个子数组
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 征服：递归排序子数组
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # 合并：合并排序后的子数组
    return merge(left_half, right_half)


def merge(left, right):
    """
    合并两个有序数组

    参数：
        left: 有序数组 1
        right: 有序数组 2

    返回：
        合并后的有序数组
    """

    i = 0
    j = 0
    merged = []

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    while i < len(left):
        merged.append(left[i])
        i += 1

    while j < len(right):
        merged.append(right[j])
        j += 1

    return merged

**代码逻辑逐行解读：**

* **行 2：**定义 `merge_sort` 函数，它接收一个待排序数组 `arr` 作为参数。
* **行 5：**递归终止条件：如果数组长度为 1 或更少，则直接返回数组。
* **行 9-12：**分解：将数组分成两个大小相等或接近相等的子数组 `left_half` 和 `right_half`。
* **行 14-15：**征服：递归调用 `merge_sort` 函数对子数组进行排序。
* **行 17：**合并：调用 `merge` 函数合并排序后的子数组。
* **行 21：**定义 `merge` 函数，它接收两个有序数组 `left` 和 `right` 作为参数。
* **行 24：**初始化三个变量：`i` 和 `j` 用于遍历 `left` 和 `right` 数组，`merged` 用于存储合并后的数组。
* **行 26-33：**比较 `left` 和 `right` 数组中的元素，将较小的元素添加到 `merged` 数组中。
* **行 35-38：**处理 `left` 和 `right` 数组中剩余的元素。
* **行 39：**返回合并后的有序数组。

**mermaid 流程图 2.1：归并排序流程**

graph LR
subgraph 分解
    A[分解数组] --> B[递归排序子数