归并排序可视化 - 分治合并动画

归并排序（Merge Sort）是一种基于分治思想的稳定排序算法。它将数组不断二分直到每个子数组只有一个元素，然后自底向上地将相邻的有序子数组合并成更大的有序数组。归并排序在任何情况下都能保证O(n log n)的时间复杂度。

当前操作

左子数组

🔗

右子数组

合并结果

算法步骤

将数组从中间分成两个子数组
对左右两个子数组分别进行归并排序
将两个有序的子数组合并成一个有序数组

合并操作是关键：使用两个指针分别指向左右子数组的起始位置，每次比较后将较小的元素放入结果数组，直到所有元素都被处理完毕。

时间与空间复杂度

情况	时间复杂度	说明
所有情况	O(n log n)	无论输入如何，时间复杂度都相同
空间复杂度	O(n)	需要额外数组存储合并结果

归并排序是稳定排序，相等元素的相对顺序保持不变。这是其相比快速排序的重要优势。

适用场景

需要稳定排序：如按多个字段排序时保持次要字段顺序
链表排序：归并排序对链表特别高效，不需要额外空间
外部排序：处理无法一次载入内存的大数据
需要保证最坏情况性能：时间复杂度恒为O(n log n)

稳定排序链表排序外部排序大数据处理

代码实现

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


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)


# 使用示例
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)
# 输出: [3, 9, 10, 27, 38, 43, 82]

public class MergeSort {
    
    /**
     * 合并两个有序子数组
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        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, temp.length);
    }
    
    /**
     * 归并排序算法
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        // 输出: [3, 9, 10, 27, 38, 43, 82]
    }
}