排序之归并排序

归并排序采用了分治法的思想。归并排序就是将序列中前后相邻的两个有序序列归并为一个有序序列。

图片来源：维基百科

• 归并排序是一种稳定的排序。
• 归并排序的平均时间复杂度为 O(nlogn)。
• 归并排序的空间复杂度为 O(n)。

归并排序的大致过程：

1. 将一个无序的序列划分为n个子序列，每个值包含1个元素。
2. 反复合并子序列生成新的有序子列，直到最后形成一个有序的序列。

merge函数

Algorithm merge(A, lo, mid, hi)   // 合并A的两个子数组，A[lo..mid], A[mid+1...hi]
  FOR n ← lo to hi                // 将数组复制到临时数组T
    T[n] ← A[n]                   
  END FOR

  j ← mid + 1, i ← lo 

  WHILE lo <= mid and j <= hi     // 对数组进行合并
    IF T[lo] <= T[j]
      A[i] ← T[lo]
      lo ← lo + 1
    ELSE
      A[i] ← T[j]
      j ← j + 1
    END IF
    i ← i + 1
  END WHILE

  WHILE lo <= mid                 // 如果左半部分有余，复制进去
    A[i] ← T[lo]
    lo ← lo + 1
    i ← i + 1
  END WHILE

  WHILE j <= hi                   // 如果右半部分有余，复制进去
    A[i] ← T[j]
    j ← j + 1
    i ← i + 1
  END WHILE
END Algorithm

自顶向下(Top-down)

自顶向下的归并：就是将序列元素不断二分，直到子数组的个数为1，然后逐级归并成一个新的有序序列。一般采用递归法。 自顶向下的实现：

Algorithm mergeSort(A, lo, hi)
  IF lo < hi
    mid ← lo + (hi - lo) / 2      // 中间值，整数
    mergeSort(A, lo, mid)
    mergeSort(A, mid + 1, hi)
    merge(arr, lo, mid, hi)
  END IF
END Algorithm

自底向上(Bottom-up)

自底向上的归并：就是把序列元素的每个元素看成一个个有序子列，然后两两归并，形成一个新的有序序列。一般采用循环迭代法。

Algorithm mergeSort(A)
  step ← 1
  WHILE step < length(A) - 1
    i ← 0 
    WHILE i < length(A) - 1
      merge(arr, i, min(i + step - 1, length(A) - 1), min(i + 2 * step - 1, length(A) - 1))
      i ← i + 2 * step
    END WHILE
    step ← step * 2
  END WHILE
END Algorithm