归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

算法原理

• 核心思想：基于 分治法（Divide and Conquer），将数组递归拆分为最小单元，再将有序子数组合并。
• 步骤：
  1. 分：将数组从中间分成左右两部分。
  2. 治：递归对左右子数组排序。
  3. 合：合并两个有序子数组为一个有序数组。
• 稳定性：稳定排序（合并时保持相同元素的相对顺序）。

---

时间复杂度

场景	时间复杂度	空间复杂度
所有情况	O(n log n)	O(n)

---

代码实现

Golang 实现

package main

import "fmt"

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    // 将剩余元素追加到结果
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    sorted := mergeSort(arr)
    fmt.Println("Sorted:", sorted)  // Output: Sorted: [11 12 22 25 34 64 90]
}

Java 实现

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);
        merge(arr, left, mid, right, temp);
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, k = 0;

        // 合并有序子数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 处理剩余元素
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        // 将合并结果复制回原数组
        System.arraycopy(temp, 0, arr, left, k);
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        mergeSort(arr);
        System.out.print("Sorted: ");
        for (int num : arr) {
            System.out.print(num + " ");  // Output: Sorted: 11 12 22 25 34 64 90 
        }
    }
}