Overview
Merge Sort is a divide-and-conquer algorithm that splits the array into smaller subarrays, sorts them, and then merges them back together. It is an efficient, stable, and comparison-based sorting algorithm.
Key Characteristics
- Time Complexity: O(n log n) for all cases (worst, average, and best).
- Space Complexity: O(n) due to the temporary arrays used for merging.
- Stability: Stable (maintains the relative order of equal elements).
- Algorithm Type: Comparison-based, divide-and-conquer sorting.
How Merge Sort Works
- Divide: Split the array into two halves.
- Conquer: Recursively sort each half.
- Combine: Merge the two sorted halves to produce the sorted array.
Steps and Example
Consider the following unsorted array:
[5, 3, 8, 4, 2]Step 1: Divide the array
- Split
[5, 3, 8, 4, 2]into[5, 3, 8]and[4, 2].
Step 2: Recursively sort each half
- Split
[5, 3, 8]into[5, 3]and[8]. - Split
[5, 3]into[5]and[3].
Step 3: Merge sorted halves
- Merge
[5]and[3]to get[3, 5]. - Merge
[3, 5]and[8]to get[3, 5, 8]. - Split
[4, 2]into[4]and[2]. - Merge
[4]and[2]to get[2, 4]. - Finally, merge
[3, 5, 8]and[2, 4]to get[2, 3, 4, 5, 8].
Visualization
Let’s generate a step-by-step visualization of Merge Sort using diagrams:
Initial Array
[5, 3, 8, 4, 2]Step 1 : Divide
[5, 3, 8, 4, 2]
/ \
[5, 3, 8] [4, 2]Step 2 : Recursively Sort
[5, 3, 8] [4, 2]
/ \ / \
[5, 3] [8] [4] [2]
/ \
[5] [3]Step 3 : Merge
Merge [5] and [3] -> [3, 5]
Merge [3, 5] and [8] -> [3, 5, 8]
Merge [4] and [2] -> [2, 4]
Merge [3, 5, 8] and [2, 4] -> [2, 3, 4, 5, 8]