Merge Sort Visualization

Watch the divide-and-conquer decomposition and merging process

Merge Sort is a stable sorting algorithm based on the divide-and-conquer principle. It repeatedly splits the array in half until each subarray has only one element, then bottom-up merges adjacent sorted subarrays into larger sorted arrays. Merge Sort guarantees O(n log n) time complexity in all cases.

🔀 Divide
→
🔗 Merge
Current Operation
Left Array
🔗
Right Array
Merge Result
Array State
Click 'Start Sorting' to view animation

Algorithm Steps

  1. Split the array into two halves at the middle
  2. Recursively merge sort both halves
  3. Merge the two sorted halves into one sorted array

The merge operation is key: use two pointers at the start of each subarray, compare and add the smaller element to the result, until all elements are processed.

Time and Space Complexity

Case Time Complexity Description
All Cases O(n log n) Time complexity is the same regardless of input
Space Complexity O(n) Extra array needed for merging

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

Use Cases

  • Stable sorting: When secondary key order must be preserved
  • Linked list sorting: Very efficient, no extra space needed
  • External sorting: Processing data too large for memory
  • Guaranteed worst-case performance: Always O(n log n)
Stable Sort Linked Lists External Sort Big Data

Implementation

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]
    }
}