Merge Sort Algorithm
Algorithm MergeSort(A, low, high)
// Sort subarray A[low..high] using Merge Sort
1. if low < high then
2. mid ← floor((low + high) / 2)
3. MergeSort(A, low, mid) // Sort left half
4. MergeSort(A, mid + 1, high) // Sort right half
5. Merge(A, low, mid, high) // Merge the two halves
end if
End MergeSort
Merge Procedure
Algorithm Merge(A, low, mid, high)
// Merge sorted subarrays A[low..mid] and A[mid+1..high]
1. n1 ← mid - low + 1
2. n2 ← high - mid
3. Create arrays L[1..n1], R[1..n2]
4. for i ← 1 to n1 do
5. L[i] ← A[low + i - 1]
6. for j ← 1 to n2 do
7. R[j] ← A[mid + j]
8. i ← 1; j ← 1; k ← low
8. while i ≤ n1 and j ≤ n2 do
9. if L[i] ≤ R[j] then
10. A[k] ← L[i]
11. i ← i + 1
12. else
13. A[k] ← R[j]
14. j ← j + 1
end if
15. k ← k + 1
end while
// Copy remaining elements of L[], if any
16. while i ≤ n1 do
17. A[k] ← L[i]
18. i ← i + 1; k ← k + 1
end while
// Copy remaining elements of R[], if any
19. while j ≤ n2 do
20. A[k] ← R[j]
21. j ← j + 1; k ← k + 1
22. end while
23. return
Step-by-step Trace on [8, 1, 4, 7, 3, 50, 26, 18, 20, 4]
Initial call: MergeSort(A, 0, 9)
Split into two halves:
Left: A[0..4] = [8, 1, 4, 7, 3]
Right: A[5..9] = [50, 26, 18, 20, 4]
Recursive calls and merges:
Call Subarray Action Result after merge
Split to [8,1,4] and
MergeSort(A,0,4) [8, 1, 4, 7, 3]
[7,3]
MergeSort(A,0,2) [8, 1, 4] Split to [8,1] and [4]
MergeSort(A,0,1) [8, 1] Split to [8] and [1]
Single element, no
MergeSort(A,0,0) [8] [8]
action
Single element, no
MergeSort(A,1,1) [1] [1]
action
Merge(A,0,0,1) Merge [8] and [1] Sort and merge [1, 8]
Single element, no
MergeSort(A,2,2) [4] [4]
action
Merge(A,0,1,2) Merge [1,8] and [4] Sort and merge [1, 4, 8]
MergeSort(A,3,4) [7, 3] Split to [7] and [3]
Single element, no
MergeSort(A,3,3) [7] [7]
action
Single element, no
MergeSort(A,4,4) [3] [3]
action
Merge(A,3,3,4) Merge [7] and [3] Sort and merge [3, 7]
Merge(A,0,2,4) Merge [1,4,8] and [3,7] Sort and merge [1, 3, 4, 7, 8]
Split to [50, 26, 18]
MergeSort(A,5,9) [50, 26, 18, 20, 4]
and [20, 4]
Call Subarray Action Result after merge
Split to [50, 26] and
MergeSort(A,5,7) [50, 26, 18]
[18]
MergeSort(A,5,6) [50, 26] Split to [50] and [26]
Single element, no
MergeSort(A,5,5) [50] [50]
action
Single element, no
MergeSort(A,6,6) [26] [26]
action
Merge(A,5,5,6) Merge [50] and [26] Sort and merge [26, 50]
Single element, no
MergeSort(A,7,7) [18] [18]
action
Merge(A,5,6,7) Merge [26, 50] and [18] Sort and merge [18, 26, 50]
MergeSort(A,8,9) [20, 4] Split to [20] and [4]
Single element, no
MergeSort(A,8,8) [20] [20]
action
Single element, no
MergeSort(A,9,9) [4] [4]
action
Merge(A,8,8,9) Merge [20] and [4] Sort and merge [4, 20]
Merge [18, 26, 50] and [4,
Merge(A,5,7,9) Sort and merge [4, 18, 20, 26, 50]
20]
Merge [1, 3, 4, 7, 8] and [1, 3, 4, 4, 7, 8,
Merge(A,0,4,9) Sort and merge 18, 20, 26, 50]
[4, 18, 20, 26, 50]
Final Sorted Array:
[1, 3, 4, 4, 7, 8, 18, 20, 26, 50]
+---------------------------------------------+
| [8 1 4 7 3 50 26 18 20 4] |
+---------------------------------------------+
/ \
+----------------------------------+ +----------------------------------+
| [8 1 4 7 3] | | [50 26 18 20 4] |
+----------------------------------+ +----------------------------------+
/ \ / \
+----------------------+ +-------------------+ +----------------------+ +----------------+
| [8 1 4] | | [7 3] | | [50 26 18] | | [20 4] |
+----------------------+ +-------------------+ +----------------------+ +----------------+
/ \ / \ / \ / \
+---------------+ +----------+ +-------+ +-------+ +------------+ +--------+ +--------+ +-------+
| [8 1] | | [4] | | [7] | | [3] | | [50 26] | | [18] | | [20] | | [4] |
+---------------+ +----------+ +-------+ +-------+ +------------+ +--------+ +--------+ +-------+
/ \
+-------+ +-------+
| [8] | | [1] |
+-------+ +-------+
--- Merge Steps ---
[8] + [1] → [1 8]
[1 8] + [4] → [1 4 8]
[7] + [3] → [3 7]
[1 4 8] + [3 7] → [1 3 4 7 8]
[50] + [26] → [26 50]
[26 50] + [18] → [18 26 50]
[20] + [4] → [4 20]
[18 26 50] + [4 20] → [4 18 20 26 50]
[1 3 4 7 8] + [4 18 20 26 50] → [1 3 4 4 7 8 18 20 26 50]