Merge Sort Explained: Stability and Time Complexity Benefits

Merge Sort is a classic divide-and-conquer algorithm whose core idea is to break down a large problem into smaller subproblems, solve the subproblems, and then merge the results to obtain a sorted dataset. Its key advantages are stable sorting (the relative order of equal elements is preserved) and a consistent time complexity of O(n log n) (regardless of whether the data is sorted or not). It is ideal for processing large-scale data, especially in scenarios like linked list sorting and external sorting (where data volume exceeds memory capacity).

Core Principles of Merge Sort

Merge Sort follows a three-step divide-conquer-merge process, taking ascending sorting as an example:

1. Divide

Recursively split the unsorted array into two equal-length subarrays until each subarray contains only one element (a single element is inherently sorted).

Example: Splitting the array [8, 3, 5, 4, 7, 6, 1, 2]:
- 1st split: [8, 3, 5, 4] and [7, 6, 1, 2]
- 2nd split: [8, 3], [5, 4], [7, 6], [1, 2]
- 3rd split: [8], [3], [5], [4], [7], [6], [1], [2] (split terminates)

2. Conquer

Recursively process each subarray until all subarrays are sorted (i.e., split down to single elements).

3. Merge

Combine two sorted subarrays into a larger sorted array, repeating this process until the entire array is merged and sorted.

Merge core: Maintain two pointers pointing to the start of the two subarrays. Compare the elements at the pointers each time, add the smaller element to the result array, and move the corresponding pointer forward until all elements are merged.

Merge Process Example (Merging `[3,8]` and `[4,5]`)

Step	Subarray 1 (Pointer i)	Subarray 2 (Pointer j)	Result Array
1	[3(i), 8]	[4(j), 5]	[3]
2	[3, 8(i)]	[4(j), 5]	[3, 4]
3	[3, 8(i)]	[4, 5(j)]	[3, 4, 5]
4	[3, 8(i)]	[4, 5] (j out of bounds)	[3, 4, 5, 8]

Merge Sort Implementations (Python)

Merge Sort implementations consist of two parts: recursive splitting and merging sorted subarrays. Below are complete, runnable code examples:

1. Basic Implementation (Ascending Sort)

python

运行

def merge_sort(arr):
    # Recursive base case: return if array length <= 1 (already sorted)
    if len(arr) <= 1:
        return arr
    
    # 1. Divide: Split the array into left and right subarrays at the midpoint
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # Recursively sort left subarray
    right = merge_sort(arr[mid:])  # Recursively sort right subarray
    
    # 2. Merge: Combine the two sorted subarrays
    return merge(left, right)

def merge(left, right):
    result = []  # Store the merged sorted array
    i = j = 0    # i: pointer for left subarray, j: pointer for right subarray
    
    # Compare elements from both subarrays and add to result in order
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= ensures sorting stability
            result.append(left[i])
            i += 1  # Move left pointer forward
        else:
            result.append(right[j])
            j += 1  # Move right pointer forward
    
    # Append remaining elements from the left or right subarray
    result.extend(left[i:])  # Remaining elements in left subarray
    result.extend(right[j:]) # Remaining elements in right subarray
    
    return result

# Test code
if __name__ == "__main__":
    unsorted_arr = [8, 3, 5, 4, 7, 6, 1, 2]
    sorted_arr = merge_sort(unsorted_arr)
    print("Original array:", unsorted_arr)
    print("Sorted array:", sorted_arr)  # Output: [1, 2, 3, 4, 5, 6, 7, 8]

2. In-Place Sort Optimization (Reduce Space Overhead)

The basic implementation creates multiple copies of subarrays, resulting in O(n) space complexity. Below is an in-place version (avoids array copying by passing index ranges):

python

运行

def merge_sort_in_place(arr):
    # Auxiliary array: used for temporary storage of merged results (created once to reduce space overhead)
    temp = [0] * len(arr)
    
    def sort(low, high):
        if low >= high:
            return
        # Divide: split down to single elements
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid + 1, high)
        # Merge: combine the two sorted intervals [low, mid] and [mid+1, high]
        merge_in_place(low, mid, high)
    
    def merge_in_place(low, mid, high):
        # Copy elements of the current interval to the auxiliary array
        for k in range(low, high + 1):
            temp[k] = arr[k]
        
        i, j = low, mid + 1  # Pointers for left and right intervals
        k = low              # Pointer for updating the original array
        
        # Merge and write back to the original array
        while i <= mid and j <= high:
            if temp[i] <= temp[j]:
                arr[k] = temp[i]
                i += 1
            else:
                arr[k] = temp[j]
                j += 1
            k += 1
        
        # Process remaining elements in the left interval
        while i <= mid:
            arr[k] = temp[i]
            i += 1
            k += 1
    
    sort(0, len(arr) - 1)
    return arr

# Test
unsorted_arr = [8, 3, 5, 4, 7, 6, 1, 2]
merge_sort_in_place(unsorted_arr)
print("In-place sorted array:", unsorted_arr)  # Output: [1, 2, 3, 4, 5, 6, 7, 8]

Time and Space Complexity

Metric	Value	Explanation
Time Complexity (Best)	O(n log n)	Full splitting and merging are required regardless of data order; complexity is stable
Time Complexity (Worst)	O(n log n)	Same as best case, no degradation risk
Time Complexity (Average)	O(n log n)	Divide-and-conquer leads to logarithmic growth in complexity
Space Complexity (Basic)	O(n)	Subarray copies during recursion + temporary array for merging
Space Complexity (In-Place)	O(n)	Only a fixed-size auxiliary array (temp) is needed; recursion stack space is O(log n) (negligible)
Stability	Stable	`<=` preserves the relative order of equal elements during merging

Pros and Cons of Merge Sort

Pros

Stability: The relative order of equal elements is preserved, making it suitable for sorting data with order requirements (e.g., records with priorities).
Stable Time Complexity: Always O(n log n) with no risk of degradation (unlike Quick Sort, which degrades to O(n²) in extreme cases).
Suitable for Large-Scale Data: The divide-and-conquer approach enables efficient processing of large datasets, and it even supports external sorting (data stored on disk, loaded into memory in batches for merging).
Ideal for Linked List Sorting: Linked lists have low random access efficiency, but Merge Sort’s merging process only requires adjusting pointers (no element movement), resulting in high efficiency.

Cons

Space Overhead: Requires additional auxiliary space (O(n)), making it unsuitable for memory-constrained scenarios.
Low Efficiency for Small Datasets: For small-scale data (n < 100), simple sorting algorithms like Insertion Sort and Bubble Sort have smaller constant overhead and are actually faster.

Real-World Applications of Merge Sort

Large-Scale Data Sorting: Such as sorting massive data in databases and preprocessing data in log analysis.
Linked List Sorting: The sorting of Java’s LinkedList and Python’s collections.deque is implemented using Merge Sort under the hood.
External Sorting: When data volume exceeds memory capacity (e.g., GB-level data), Merge Sort is the first choice—split the data into small chunks (fit in memory), sort each chunk separately, and then merge them.
Multi-Way Merge: Extended to merging multiple sorted arrays (e.g., merging database query results, data aggregation in distributed systems).
Inversion Counting: The merging process of Merge Sort can efficiently count the number of inversions in an array (e.g., counting the number of pairs where “i < j and arr[i] > arr[j]”).

Summary

Implementation points: Split down to single elements, merge two sorted subarrays with double pointers, and pay attention to preserving stability and optimizing space overhead.

The core of Merge Sort is the divide-and-conquer idea: break down into subproblems → solve subproblems → merge results.

Key features: stable sorting + O(n log n) stable time complexity, suitable for large-scale data and linked lists.