# 归并排序 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法： - 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）； - 自下而上的迭代； 在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为： > However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle. > > 然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。 说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。 和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。 ## 2. 算法步骤 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列； 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置； 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置； 4. 重复步骤 3 直到某一指针达到序列尾； 5. 将另一序列剩下的所有元素直接复制到合并序列尾。 ## 3. 动图演示  ## 4. JavaScript 代码实现 ```js 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[0] <= right[0]) { 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 代码实现 ```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[0] <= right[0]: 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 代码实现 ```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[0] <= right[0] { result = append(result, left[0]) left = left[1:] } else { result = append(result, right[0]) right = right[1:] } } for len(left) != 0 { result = append(result, left[0]) left = left[1:] } for len(right) != 0 { result = append(result, right[0]) right = right[1:] } return result } ``` ## 7. Java 代码实现 ```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[0] <= right[0]) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } else { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } } while (left.length > 0) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } while (right.length > 0) { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } return result; } } ``` ## 8. PHP 代码实现 ```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[0] <= $right[0]) { $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; } ```