• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

# 2. 算法步骤

1. 1.
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 2.
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 3.
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 4.
重复步骤 3 直到某一指针达到序列尾；
5. 5.
将另一序列剩下的所有元素直接复制到合并序列尾。

# 3. 动图演示 # 4. JavaScript 代码实现

1
function mergeSort(arr) { // 采用自上而下的递归方法
2
var len = arr.length;
3
if(len < 2) {
4
return arr;
5
}
6
var middle = Math.floor(len / 2),
7
left = arr.slice(0, middle),
8
right = arr.slice(middle);
9
return merge(mergeSort(left), mergeSort(right));
10
}
11
12
function merge(left, right)
13
{
14
var result = [];
15
16
while (left.length && right.length) {
17
if (left <= right) {
18
result.push(left.shift());
19
} else {
20
result.push(right.shift());
21
}
22
}
23
24
while (left.length)
25
result.push(left.shift());
26
27
while (right.length)
28
result.push(right.shift());
29
30
return result;
31
}
Copied!

# 5. Python 代码实现

1
def mergeSort(arr):
2
import math
3
if(len(arr)<2):
4
return arr
5
middle = math.floor(len(arr)/2)
6
left, right = arr[0:middle], arr[middle:]
7
return merge(mergeSort(left), mergeSort(right))
8
9
def merge(left,right):
10
result = []
11
while left and right:
12
if left <= right:
13
result.append(left.pop(0));
14
else:
15
result.append(right.pop(0));
16
while left:
17
result.append(left.pop(0));
18
while right:
19
result.append(right.pop(0));
20
return result
Copied!

# 6. Go 代码实现

1
func mergeSort(arr []int) []int {
2
length := len(arr)
3
if length < 2 {
4
return arr
5
}
6
middle := length / 2
7
left := arr[0:middle]
8
right := arr[middle:]
9
return merge(mergeSort(left), mergeSort(right))
10
}
11
12
func merge(left []int, right []int) []int {
13
var result []int
14
for len(left) != 0 && len(right) != 0 {
15
if left <= right {
16
result = append(result, left)
17
left = left[1:]
18
} else {
19
result = append(result, right)
20
right = right[1:]
21
}
22
}
23
24
for len(left) != 0 {
25
result = append(result, left)
26
left = left[1:]
27
}
28
29
for len(right) != 0 {
30
result = append(result, right)
31
right = right[1:]
32
}
33
34
return result
35
}
Copied!

# 7. Java 代码实现

1
public class MergeSort implements IArraySort {
2
3
@Override
4
public int[] sort(int[] sourceArray) throws Exception {
5
// 对 arr 进行拷贝，不改变参数内容
6
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8
if (arr.length < 2) {
9
return arr;
10
}
11
int middle = (int) Math.floor(arr.length / 2);
12
13
int[] left = Arrays.copyOfRange(arr, 0, middle);
14
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
15
16
return merge(sort(left), sort(right));
17
}
18
19
protected int[] merge(int[] left, int[] right) {
20
int[] result = new int[left.length + right.length];
21
int i = 0;
22
while (left.length > 0 && right.length > 0) {
23
if (left <= right) {
24
result[i++] = left;
25
left = Arrays.copyOfRange(left, 1, left.length);
26
} else {
27
result[i++] = right;
28
right = Arrays.copyOfRange(right, 1, right.length);
29
}
30
}
31
32
while (left.length > 0) {
33
result[i++] = left;
34
left = Arrays.copyOfRange(left, 1, left.length);
35
}
36
37
while (right.length > 0) {
38
result[i++] = right;
39
right = Arrays.copyOfRange(right, 1, right.length);
40
}
41
42
return result;
43
}
44
45
}
Copied!

# 8. PHP 代码实现

1
function mergeSort(\$arr)
2
{
3
\$len = count(\$arr);
4
if (\$len < 2) {
5
return \$arr;
6
}
7
\$middle = floor(\$len / 2);
8
\$left = array_slice(\$arr, 0, \$middle);
9
\$right = array_slice(\$arr, \$middle);
10
return merge(mergeSort(\$left), mergeSort(\$right));
11
}
12
13
function merge(\$left, \$right)
14
{
15
\$result = [];
16
17
while (count(\$left) > 0 && count(\$right) > 0) {
18
if (\$left <= \$right) {
19
\$result[] = array_shift(\$left);
20
} else {
21
\$result[] = array_shift(\$right);
22
}
23
}
24
25
while (count(\$left))
26
\$result[] = array_shift(\$left);
27
28
while (count(\$right))
29
\$result[] = array_shift(\$right);
30
31
return \$result;
32
}
Copied!