The merge sort algorithm is a common example of the divide-and-conquer approach to algorithm design. This approach usually boils down to three steps: divide the problem into subproblems with are of the same type as the original problem, conquer the subproblems solving them via recursion, and combine the solutions of the subproblems into a solution for the problem we started with. In this context, the merge algorithm first divides an array into smaller arrays, sorts each of those arrays using merge sort (i.e., recursively), and then just merges the two smaller sorted arrays to get the original array in a sorted fashion. The most important part of this algorithm is the merging procedure, which we can explain once again by using the deck of cards analogy! Assume that there are two sorted piles of cards both having the smallest card on the top. If we want to merge these into a single sorted pile of cards, the procedure is straightforward: we simply pick the smaller card among the two piles, place it in a new pile, and interate this process until there are no more cards left. That’s how the merging step happens for merge sort. This algorithm has one nice property where it’s best, worst and average cases time complexities match and are equal to $O(n \log n)$.
Pseudocode
We can describe the algorithm in pseudocode (assuming array indexes start in 1) as follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| MERGE-SORT(A, p, r)
if p < r
q = floor( (p + r) / 2 )
MERGE-SORT(A, p, q)
MERGE-SORT(A, q+1, r)
MERGE(A, p, q, r)
MERGE(A, p, q, r)
n1 = q - p + 1
n2 = r - q
L[1,..., n1 +1] new empty array
R[1,..., n2 +1] new empty array
for i = 1 to n1
L[i] = A[p + i - 1]
For j = 1 to n2
R[j] = A[q + j]
L[n1 + 1] = infinity
R[n2 + 1] = infinity
i = 1
j = 1
for k = p to r
if L[i] <= R[j]
A[k] = L[i]
i++
else
A[k] = R[j]
j++
|
Implementation
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| import math
def merge(array, p, q, r):
n1, n2 = q - p + 1, r - q
left = [0] * (n1+1)
right = [0] * (n2+1)
for i in range(0, n1):
left[i] = array[p+i]
for j in range(0, n2):
right[j] = array[q+j+1]
left[n1] = float('inf')
right[n2] = float('inf')
i, j = 0, 0
for k in range(p, r+1):
if left[i] <= right[j]:
array[k] = left[i]
i += 1
else:
array[k] = right[j]
j += 1
def merge_sort(array, p, r):
if p<r:
q = math.floor((p+r)/2)
merge_sort(array, p, q)
merge_sort(array, q+1, r)
merge(array, p, q, r)
array = [43, 2, 21, 3, 70, 8]
merge_sort(array, 0, 5)
print(array)
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| package main
import (
"fmt"
"math"
)
func merge(array []float64, p, q, r int) {
n1, n2 := q-p+1, r-q
left := make([]float64, n1+1)
right := make([]float64, n1+1)
for i := 0; i < n1; i++ {
left[i] = array[p+i]
}
for j := 0; j < n2; j++ {
right[j] = array[q+j+1]
}
left[n1] = math.Inf(1)
right[n2] = math.Inf(1)
i, j := 0, 0
for k := p; k <= r; k++ {
if left[i] <= right[j] {
array[k] = left[i]
i++
} else {
array[k] = right[j]
j++
}
}
}
func mergeSort(array []float64, p, r int) {
if p < r {
q := (p + r) / 2
mergeSort(array, p, q)
mergeSort(array, q+1, r)
merge(array, p, q, r)
}
}
func main() {
array := []float64{43, 2, 21, 3, 70, 8}
mergeSort(array, 0, 5)
fmt.Println(array)
}
|
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| fn merge(array: &mut Vec<f64>, p: usize, q: usize, r: usize) {
let n1: usize = q-p+1;
let n2: usize = r-q;
let mut left: Vec<f64> = Vec::new();
let mut right: Vec<f64> = Vec::new();
for i in 0..n1 {
left.push(array[p+i]);
}
for j in 0..n2 {
right.push(array[q+j+1]);
}
left.push(1.0/0.0);
right.push(1.0/0.0);
let mut i: usize = 0;
let mut j: usize = 0;
for k in p..r+1 {
if left[i] <= right[j] {
array[k] = left[i];
i += 1;
} else {
array[k] = right[j];
j += 1;
}
}
}
fn merge_sort(array: &mut Vec<f64>, p: usize, r: usize) {
if p < r {
let q = (p + r) / 2;
merge_sort(array, p, q);
merge_sort(array, q+1, r);
merge(array, p, q, r);
}
}
fn main() {
let mut array: Vec<f64> = [43.0, 2.0, 21.0, 3.0, 70.0, 8.0].to_vec();
merge_sort(&mut array, 0, 5);
println!("{:?}", array);
}
|
References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition