Merge Sort is a classic sorting algorithm based on the “Divide and Conquer” paradigm, making it an excellent choice for beginners to understand the combination of divide-and-conquer strategies and recursion. It solves complex problems by breaking them into simpler subproblems, resolving each, and then merging the results to achieve efficient sorting.
I. Divide and Conquer: From “Big Problems” to “Small Problems”¶
The core of “Divide and Conquer” is “Divide, Solve, Merge”: Break a large problem into smaller subproblems, solve each subproblem individually, and then combine the results.
Analogy with Real Life: Organizing a messy deck of 52 cards:
1. Divide: Split the 52 cards into two heaps of 26, then split each heap into smaller heaps of 13, and so on, until each heap has 1 card (naturally sorted).
2. Conquer: Merge the smallest heaps (1 card) into pairs (2 cards), then into 4-card heaps, 8-card heaps, etc., until the entire sorted deck is formed.
Analogy with Array Sorting: Split the array into two halves, recursively sort each half, and finally merge them into a single sorted array.
II. Core Steps of Merge Sort¶
Merge Sort consists of two key steps: “Divide” and “Merge”:
1. Divide: Recursively Split the Array¶
- If the array length is ≤ 1, return it directly (a single element is already sorted).
- Otherwise, find the middle index
mid, split the array into left halfleftand right halfright. - Recursively divide the left and right halves until all subarrays have length 1.
Example: For the array [5, 3, 8, 6, 2, 7, 1, 4]:
- First division: Mid = 3, split into left = [5, 3, 8, 6] and right = [2, 7, 1, 4].
- Recursively divide until all subarrays are length 1: [5], [3], [8], [6], [2], [7], [1], [4].
2. Merge: Merge Sorted Subarrays¶
Once subarrays are split into length 1, merge adjacent sorted subarrays while maintaining order:
- Use two pointers i and j to track the start of each subarray.
- Compare elements at i and j, add the smaller element to a temporary array, and move the corresponding pointer.
- Repeat until one subarray is fully traversed, then append the remaining elements.
- Finally, copy the temporary array back to the original array.
Merge Process Example:
Merging [5] and [3]:
- Pointers: i=0 (5), j=0 (3).
- Compare: 3 < 5, add to temp array → [3], then j=1 (right subarray exhausted).
- Append remaining element [5] → temp array [3,5], copy back to original array → [3,5].
III. Complete Merge Sort Process (Example: [5,3,8,6,2,7,1,4])¶
- Divide: Recursively split into 8 subarrays of length 1.
- First Merge Layer: Merge pairs to get 4 sorted subarrays:
[3,5],[6,8],[2,7],[1,4]. - Second Merge Layer: Merge again to get 2 sorted subarrays:
[3,5,6,8],[1,2,4,7]. - Final Merge: Combine the two arrays to get the fully sorted array:
[1,2,3,4,5,6,7,8].
IV. Time and Space Complexity¶
- Time Complexity: The recursion depth is
O(log n)(each split halves the array size), and merging each level takesO(n)time. Thus, the total time complexity isO(n log n)(stable for all input orders). - Space Complexity: Temporary arrays are needed for merging, resulting in an extra space of
O(n).
V. Stability: A Key Advantage of Merge Sort¶
Merge Sort is a stable sort: When merging subarrays with equal elements (e.g., [2,2]), the left subarray’s element is prioritized, preserving the relative order of equal elements.
VI. Summary¶
Merge Sort simplifies complex sorting problems using the “Divide and Conquer” paradigm, with core steps of “Divide → Recurse → Merge”. It elegantly demonstrates how to break large problems into solvable subproblems, making it an excellent case study for understanding divide-and-conquer algorithms. Despite requiring extra space, its stable O(n log n) time complexity makes it suitable for large datasets or scenarios requiring stable sorting.
With clear principles and step-by-step examples, this article should help you fully grasp the core logic of Merge Sort!