Merge Sort 终极指南：分而治之算法

Source: Dev.to

介绍

归并排序是一种基于 分治 范式的排序算法。它递归地将数组划分为两半，直到达到单个元素（按定义已排序），随后有序地将它们合并。它在所有情况下都能保证 O(n log n) 的性能。

该算法（也称为 归并排序）是计算机科学中排序的基石之一。当我们需要 稳定性 和 性能保证 时，它尤为突出。

算法阶段

1. Divide
   数组被递归地一分为二，直到达到单个元素，这些元素被视为已经有序。

2. Conquista (Conquer)
   每个子‑划分独立地被解决并排序。

3. Combina (Merge)
   使用 two‑pointers 技术将各部分合并或“混合”，确保合并后的结果仍然保持有序。

与流行的 QuickSort 不同，Merge Sort 在任何情况下（最佳情况、平均情况和最坏情况）始终保证运行时间复杂度为 O(n log n)。然而，这种稳定的性能代价是更高的 RAM 内存使用。

可读的 Go 实现

func sortList(unsortedList []int) []int {
    n := len(unsortedList)
    if n <= 1 {
        return unsortedList
    }

    midpoint := n / 2
    leftList := sortList(unsortedList[:midpoint])
    rightList := sortList(unsortedList[midpoint:])

    resultList := make([]int, 0, n)
    leftPointer, rightPointer := 0, 0

    for leftPointer < midpoint || rightPointer < n-midpoint {
        if leftPointer == midpoint {
            resultList = append(resultList, rightList[rightPointer])
            rightPointer++
        } else if rightPointer == n-midpoint {
            resultList = append(resultList, leftList[leftPointer])
            leftPointer++
        } else if leftList[leftPointer] <= rightList[rightPointer] {
            resultList = append(resultList, leftList[leftPointer])
            leftPointer++
        } else {
            resultList = append(resultList, rightList[rightPointer])
            rightPointer++
        }
    }
    return resultList
}

这个版本清晰且易于调试，但在每次递归调用时都会创建一个新的 slice，这会导致动态内存分配并对 garbage collector 产生压力。

使用共享缓冲区模式进行优化

对于高并发环境或标准库，最好分配 唯一的辅助缓冲区，在整个递归过程中重复使用它。

func SortList(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    // Un solo buffer auxiliar compartido para toda la ejecución
    temp := make([]int, len(arr))
    mergeSort(arr, temp, 0, len(arr)-1)
    return arr
}

func mergeSort(arr, temp []int, left, right int) {
    if left < right {
        mid := left + (right-left)/2

        mergeSort(arr, temp, left, mid)
        mergeSort(arr, temp, mid+1, right)

        merge(arr, temp, left, mid, right)
    }
}

func merge(arr, temp []int, left, mid, right int) {
    // Copiar el segmento actual al buffer temporal
    for i := left; i <= right; i++ {
        temp[i] = arr[i]
    }

    i, j, k := left, mid+1, left

    // Fusionar de nuevo en el arreglo original
    for i <= mid && j <= right {
        if temp[i] <= temp[j] {
            arr[k] = temp[i]
            i++
        } else {
            arr[k] = temp[j]
            j++
        }
        k++
    }

    // Copiar los elementos restantes del sub‑arreglo izquierdo (si los hay)
    for i <= mid {
        arr[k] = temp[i]
        i++
        k++
    }
}

采用此方法，额外内存严格保持在 O(N)；无论进行多少次合并或划分，都不会超过原始缓冲区的大小。

结论

Merge Sort 以其数学上的稳健性和运行时间的稳定表现而著称。虽然其内存消耗常常使开发者倾向于使用 QuickSort，但 Shared Buffer Pattern 等技术可以显著降低开销，使 Merge Sort 再次占据重要位置，尤其在以下场景中：

• 链表排序，其中顺序访问是自然的。
• 需要 稳定性 和 大规模保证性能 的应用。