时间复杂度: O(nLog^n)
    归并算法是一种分治算法，思想是将原始数组切分成较小的数组，直到每个数组只有一个位置，接着将小数组合并成较大的数组，直到最后只有一个排序完毕的数组

    JavaScript

    1. const arr = [4,77,2,5,33,4,2,7,9,4,666,333,2,555,66,4,234]
    3. function mergeSortRec (arr) {
    4.   let length = arr.length
    5.   if (length === 1) {
    6.     return arr
    7.   }
    8.   let mid = Math.floor(length / 2)
    9.   let left = arr.slice(0, mid)
    10.   let right = arr.slice(mid, length)
    11.   return merge(mergeSortRec(left),mergeSortRec(right))
    12. }
    13. function merge(left, right) {
    14.   var result = [];
    15.   let il = 0;
    16.   let ir = 0;
    17.   while (il < left.length && ir < right.length) {
    18.     if (left[il] < right[ir]) {
    19.       result.push(left[il])
    20.       il++
    21.     }else{
    22.       result.push(right[ir])
    23.       ir++
    24.     }
    25.   }
    26.   while (il < left.length) {
    27.     result.push(left[il])
    28.     il++
    29.   }
    30.   while (ir < right.length) {
    31.     result.push(right[ir])
    32.     ir++
    33.   }
    34.   return result
    35. }
    37. console.log('mergeSortRec(arr) >>> ' ,mergeSortRec(arr));

    Swift

    2.     func mergeSortRec(arr: Array<Int>) -> Array<Int> {
    3.         let length = arr.count
    4.         if length == 1 {
    5.             return arr
    6.         }
    7.         let mid: Int = arr.count / 2
    8.         let left:Array<Int> = Array(arr[(0 ..< mid)])
    9.         let right:Array<Int> = Array(arr[(mid ..< length)])
    10.         return mergeSort(left: mergeSortRec(arr: left), right: mergeSortRec(arr: right))
    11.     }
    13.     func mergeSort(left:Array<Int>, right: Array<Int>) -> Array<Int> {
    14.         var result:Array<Int> = []
    15.         var il = 0
    16.         var ir  = 0
    17.         while il < left.count && ir < right.count {
    18.             if left[il] < right[ir] {
    19.                 result.append(left[il])
    20.                 il = il + 1
    21.             }else{
    22.                 result.append(right[ir])
    23.                 ir = ir + 1
    24.             }
    25.         }
    26.         while il < left.count {
    27.             result.append(left[il])
    28.             il = il + 1
    29.         }
    30.         while ir < right.count {
    31.             result.append(right[ir])
    32.             ir = ir + 1
    33.         }
    34.         return result
    35.     }