归并排序

关键操作是合并两个已排序的序列。

merge方法伪代码，假设A[p...q]和A[q+1...r]都已经排序好。

MERGE(A,p,q,r)

n1 = q-p+1;

n2 = r-q;

let L[1...n1+1] and R[1...n2+1] be new arrays

for i=1 to n1

L[i] = A[p+i-1]

for j=1 to n2

R[j] = A[q+j]

L[n1+1] = INT_MAX;

R[n2+1] = INT_MAX;

i=1;

j=1;

for k = p to r

if L[i] <= R[j]

A[k] = L[i];

i++;

else

A[k] = R[j]

j++;

MERGE-SORT(A,p,r)

if p[InvalidCharacterError: "R<" did not match the Name production]

Merge过程需要消耗O(n)，也几乎是唯一的消耗

我们递归地求解2个规模为n/2的子问题，所以时间为2T(n/2)

递归树有 lgn + 1 层，每层的代价均为n, 总代价为 nlgn + n

分治：将问题划分成一些子问题，子问题的形式与原问题一样，只是规模更小。