排序的黄金标准：O(N log N)

背景

在之前的文章中，我们已经掌握了：

• 二分查找 – 时间复杂度 O(log N)
• 线性效率 – 时间复杂度 O(N)

现在，我们来谈谈排序的黄金标准：时间复杂度 O(N log N)（线性对数）。

所有需要在大数据量下扩展的排序算法（如 Merge Sort 或 Quick Sort）的目标都是这个复杂度，因为它结合了：

• 将问题划分的力量（log N）
• 线性处理结果的效率（N）

Merge Sort 如何达到 O(N log N)

Merge Sort（归并排序）是 分治（Divide and Conquer）的经典示例。它分为两个阶段，这两阶段直接对应其 O(N log N) 复杂度：

1. 递归划分

   • 算法把列表不断对半划分，直到只剩下单个元素的子列表（基准情形）。
   • 例如：对 1 000 000 条数据，只需要 ≈ 20 次划分（log₂ 1 000 000 ≈ 20）。
   • 这里的 log N 表示递归树的高度。

2. 合并

   • 在递归的每一层（共 log N 层）中，算法把已排序的子列表合并回更大的有序列表。
   • 合并两段总计 N 个元素的列表，最多需要 N 次比较。
   • 这一步本质上是 O(N)（线性）的。

因为在每个 log N 层都完成一次 O(N) 的工作，整体复杂度就是 O(N log N)。

Elixir 中的 O(N)：merge 函数

实现高效的 Merge Sort 的关键是确保合并函数严格为 O(N)。在 Elixir 中，这意味着：

• 切勿使用慢速的连接操作符 (++)
• 只在列表的头部进行操作

合并代码

## --- O(N) 合并的核心 ---

## 当其中一个列表耗尽时的基准情形：
defp merge([], list_b), do: list_b
defp merge(list_a, []), do: list_a

## 主递归子句
defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
  if h_a <= h_b do
    # h_a 更小：放在结果前面并继续递归
    # 使用 A 的尾部 (t_a) 和完整的 B 列表 (list_b)。
    [h_a | merge(t_a, list_b)]
  else
    # h_b 更小：放在结果前面并继续递归
    # 使用完整的 A 列表 (list_a) 和 B 的尾部 (t_b)。
    [h_b | merge(list_a, t_b)]
  end
end

完整的 Merge Sort 实现

defmodule MergeSort do
  @doc "Elixir 中的 Merge Sort 实现（O(N log N)）。"
  def sort(list) do
    case list do
      [] -> []                     # 基准情形
      [_] -> list                  # 基准情形
      _ ->
        # 1. 划分
        {low, high} = split_list(list)

        # 2. 递归
        sorted_low  = sort(low)
        sorted_high = sort(high)

        # 3. 合并
        merge(sorted_low, sorted_high)
    end
  end

  ## 🛠️ 辅助划分函数（为了解决错误而添加）
  # O(N) 用于获取长度并划分链表。
  defp split_list(list) do
    # 找到列表的中点
    len = length(list)
    split_point = trunc(len / 2)

    # Enum.split 在指定位置进行划分（遍历列表 O(N)）
    Enum.split(list, split_point)
  end

  # 合并函数（上面定义的）
  defp merge([], list_b), do: list_b
  defp merge(list_a, []), do: list_a

  defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
    if h_a <= h_b do
      [h_a | merge(t_a, list_b)]
    else
      [h_b | merge(list_a, t_b)]
    end
  end
end

结论

Merge Sort 是我们能做到的最好的通用排序算法。它在所有情形（最坏、平均、最好）下都保证 O(N log N) 的性能，使其极其稳定可靠。

下一篇 – 高级的 O(N) 应用：我们将使用 双指针 技巧来解决 Squares of a Sorted Array 问题，将原本需要 O(N log N) 排序的需求转化为一次优雅的 O(N) 操作。同时，我们还会揭示 Elixir Map 的 O(1) 秘密（HAMT 结构）。