Algorithm Code
Time: O(n log n) | Space: O(n)
1function mergeSort(arr) {
2 if (arr.length <= 1) {
3 return arr
4 }
5
6 mid = Math.floor(arr.length / 2)
7 left = mergeSort(arr.slice(0, mid))
8 right = mergeSort(arr.slice(mid))
9
10 return merge(left, right)
11}
12
13function merge(left, right) {
14 result = []
15 i = 0, j = 0
16
17 while (i < left.length && j < right.length) {
18 if (left[i] <= right[j]) {
19 result.push(left[i])
20 i++
21 } else {
22 result.push(right[j])
23 j++
24 }
25 }
26
27 while (i < left.length) {
28 result.push(left[i])
29 i++
30 }
31
32 while (j < right.length) {
33 result.push(right[j])
34 j++
35 }
36
37 return result
38}Algorithm Steps
Step 1 of 46
1
Initial unsorted array
2
Divide array [64, 34, 25, 12, 22, 11, 90] at level 0
3
Divide array [64, 34, 25] at level 1
4
Base case: array of size 1
5
Divide array [34, 25] at level 2
6
Base case: array of size 1
7
Base case: array of size 1
8
Start merging [34] and [25]
9
Compare 34 > 25: take 25
10
Add remaining element 34 from left
11
Merged result: [25, 34]
12
Start merging [64] and [25, 34]
13
Compare 64 > 25: take 25
14
Compare 64 > 34: take 34
15
Add remaining element 64 from left
16
Merged result: [25, 34, 64]
17
Divide array [12, 22, 11, 90] at level 1
18
Divide array [12, 22] at level 2
19
Base case: array of size 1
20
Base case: array of size 1
21
Start merging [12] and [22]
22
Compare 12 ≤ 22: take 12
23
Add remaining element 22 from right
24
Merged result: [12, 22]
25
Divide array [11, 90] at level 2
26
Base case: array of size 1
27
Base case: array of size 1
28
Start merging [11] and [90]
29
Compare 11 ≤ 90: take 11
30
Add remaining element 90 from right
31
Merged result: [11, 90]
32
Start merging [12, 22] and [11, 90]
33
Compare 12 > 11: take 11
34
Compare 12 ≤ 90: take 12
35
Compare 22 ≤ 90: take 22
36
Add remaining element 90 from right
37
Merged result: [11, 12, 22, 90]
38
Start merging [25, 34, 64] and [11, 12, 22, 90]
39
Compare 25 > 11: take 11
40
Compare 25 > 12: take 12
41
Compare 25 > 22: take 22
42
Compare 25 ≤ 90: take 25
43
Compare 34 ≤ 90: take 34
44
Compare 64 ≤ 90: take 64
45
Add remaining element 90 from right
46
Merged result: [11, 12, 22, 25, 34, 64, 90]
Merge Sort Visualization
Phase: Divide |
64
0
34
1
25
2
12
3
22
4
11
5
90
6
Normal
Dividing
Left Array
Right Array
Comparing
Merging
Merged
Sorted
Step 0 of 450%
0.25x4x