• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 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.
将另一序列剩下的所有元素直接复制到合并序列尾。

# 4. JavaScript 代码实现

function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left <= right) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}

# 5. Python 代码实现

def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left <= right:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result

# 6. Go 代码实现

func mergeSort(arr []int) []int {
length := len(arr)
if length < 2 {
return arr
}
middle := length / 2
left := arr[0:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left <= right {
result = append(result, left)
left = left[1:]
} else {
result = append(result, right)
right = right[1:]
}
}
for len(left) != 0 {
result = append(result, left)
left = left[1:]
}
for len(right) != 0 {
result = append(result, right)
right = right[1:]
}
return result
}

# 7. Java 代码实现

public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left <= right) {
result[i++] = left;
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right;
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left;
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right;
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}

# 8. PHP 代码实现

function mergeSort(\$arr)
{
\$len = count(\$arr);
if (\$len < 2) {
return \$arr;
}
\$middle = floor(\$len / 2);
\$left = array_slice(\$arr, 0, \$middle);
\$right = array_slice(\$arr, \$middle);
return merge(mergeSort(\$left), mergeSort(\$right));
}
function merge(\$left, \$right)
{
\$result = [];
while (count(\$left) > 0 && count(\$right) > 0) {
if (\$left <= \$right) {
\$result[] = array_shift(\$left);
} else {
\$result[] = array_shift(\$right);
}
}
while (count(\$left))
\$result[] = array_shift(\$left);
while (count(\$right))
\$result[] = array_shift(\$right);
return \$result;
}

# 9. C++ 代码实现

void merge(vector<int>& arr, int l, int mid, int r) {
int index = 0;
int ptrL = l;
int ptrR = mid;
static vector<int>tempary;
if (arr.size() > tempary.size()) {
tempary.resize(arr.size());
}
while (ptrL != mid && ptrR != r) {
if (arr[ptrL] < arr[ptrR]) {
tempary[index++] = arr[ptrL++];
} else {
tempary[index++] = arr[ptrR++];
}
}
while (ptrL != mid) {
tempary[index++] = arr[ptrL++];
}
while (ptrR != r) {
tempary[index++] = arr[ptrR++];
}
copy(tempary.begin(), tempary.begin() + index, arr.begin() + l);
}
void mergeSort(vector<int>& arr, int l, int r) { // sort the range [l, r) in arr
if (r - l <= 1) {
return;
}
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid, r);
merge(arr, l, mid, r);
}