归并排序 merge sort

归并排序应用了分治策略。

 

算法步骤：

     分解Divide：将n个元素分成各含2/n个元素的子序列

     解决Conquer：用归并排序法对两个子序列递归的排序

     合并Combine：合并两个已排序的子序列以得到排序结果。

 

MERGE-SORT(A, p, r)
1 if p <  r
2   then q ← ⌊ (p +  r)/2 ⌋ 
3        MERGE-SORT( A, p, q)
4        MERGE-SORT( A, q + 1, r)
5        MERGE( A, p, q, r)

 

Merge-Sort（A,p,r）对子数组A[p..r]进行排序。各个递归的函数都是在同一数组上排序。如果p≥r，说明数组内只有一个元素，说明已经排好序了，退出merge-sort()。

 

MERGE(A, p, q, r)
1  n1  ← q -  p + 1
2  n2  ← r -  q
3  create arrays  L[1   n1  + 1] and  R[1   n2  + 1]
4  for  i ← 1  to n1       
5       do L[i] ← A[p +  i - 1]
6  for  j ← 1  to n2 
7       do R[j] ← A[q +  j]
8  L[n1  + 1] ← ∞           //底部放置“哨兵牌”sentinel card
9  R[n2  + 1] ← ∞
10  i ← 1
11  j ← 1
12  for  k ← p to r
13       do if  L[i] ≤ R[j]
14              then A[k] ← L[i]
15                   i ← i + 1
16              else A[k] ← R[j]
17                   j ← j + 1 

 

Merge，把两个已排好序的数组A[p..q]和A[q+1..r]合并成数组A[p..r]。Merge的时间：O(n)

示例：

 

时间分析

　　

　　常量c代表规模为1的问题所需的时间。

　　

　　为递归式T(n) = 2T(n/2) + cn构造一颗递归树。上图中，树深度为lg n，共有lg n+1层。每层的代价（合并时间）为cn。所以总代价为cn(lg n+1)

 

所以运行时间为 O(n lg n) ，此处 lg n代表 log₂n

因为对数函数的增长速度比任何线性函数增长的都要慢，所以归并排序比插入排序好。