归并排序 §

归并排序是一种通过递归思想实现的排序方法。将数组不断二分，分割成小块；然后根据分割的顺序两两组合小块，在组合的过程中对元素进行排序，最终合并成一整个有序数组。

代码实现 §

归并排序的实现需要用到两个子函数，sort()和merge()，分别对应上图中分解和合并的两个阶段。

public void mergeSort(int[] arr) {  
    sort(arr, 0, arr.length - 1);  
}  
  
private void sort(int[] arr, int start, int end) {  
    if (start == end) {  
        return;  
    }  
    int mid = start + ((end - start) >> 1);  
  
    sort(arr, start, mid);  
    sort(arr, mid + 1, end);  
    merge(arr, start, mid, end);  
}  
  
private void merge(int[] arr, int start, int mid, int end) {  
    int[] tmp = new int[end - start + 1];  
    int p1 = start;  
    int p2 = mid + 1;  
    int i = 0;  
  
    for (; p1 <= mid && p2 <= end; i++) {
        tmp[i] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; 
    } 
    while (p1 <= mid) {  
        tmp[i++] = arr[p1++];  
    }  
    while (p2 <= end) {  
        tmp[i++] = arr[p2++];  
    }  
  
    System.arraycopy(tmp, 0, arr, start, tmp.length);  
}

时空复杂度 §

• 时间复杂度：整个算法的递归次数是logn次，每一层合并所需要的总时间复杂度为O(n)，故整个归并排序的时间复杂度为O(nlogn)。
• 空间复杂度：合并阶段创建临时数组需要额外空间，空间复杂度为O(n)。

与快速排序比较 §

• 归并排序是稳定的排序算法，快速排序不稳定。
• 归并排序的时间复杂度稳定在O(nlogn)；快速排序大部分情况下时间复杂度为O(nlogn)，极端条件下会退化为O(n^2)。
• 归并排序的空间复杂度为O(n)，快速排序为常数级。这是实际应用中通常使用快速排序，而非归并排序的原因。