《算法导论》第三版 2.3.1 归并排序

MERGE-SORT(A,p,r)

if p<r
    q = (p+r)/2
    MERGE-SORT(A,p,q)
    MERGE-SORT(A,q+1,r)
    MERGE(A,p,q,r)

归并排序利用递归将一个大数组不断的从中间对半分成两个小的数组直到数组中只剩下一个元素，然后通过MERGE函数合并。
MERGE-SORT中A是数组，p是数组中需要比较的第一个元素的下标，r是最后一个元素的下标。

if p<r

就是用来判断，数组区间长度是否大于1，否则直接返回

MERGE-SORT(A,p,q)

q是区间中间元素的下标，将分开后的区间右边部分用MERGE-SORT函数处理(也就是继续分割为两半，直到区间只剩下一个元素)。下一个语句是处理左半边。
当这两个函数返回后，由他们处理的区间都已经按顺序排列（只有一个元素的数列当然是已经排好序的），MERGE函数做的只是间这两个区间合并。

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]=∞
R[n2+1]=∞
i=1
j=1
for k=p to r
    if L[i]<=R[j]
        A[k]=L[i]
        i=i+1
    else
        A[k]=R[j]
        j=j+1

n1是左边的最后一个元素的下标，n2是右边最后一个元素的下标，将左右两边的元素分别赋值给L和R，在最后设置一个无穷大的值，这样当L或R其中一个数组的元素已经全部插入完毕后(实际代码中可以通过判断i和j的值来判断)，就只会插入剩下那个数组中的元素。

i=1
j=1
for k=p to r
    if L[i]<=R[j]
        A[k]=L[i]
        i=i+1
    else
        A[k]=R[j]
        j=j+1

上述代码就是插入的过程，将L和R的值按从小到大的顺序重新放入到数组A相应的区间中。

---

这个递归顺序是先一直往左到开头，然后逐步往右

下面给一个例子方便理解:

A: 5 2 4 7 1 3 2 6

→MERGE-SORT(左边) 5   2   4   7
    →MERGE-SORT(左边) 5   2
        →MERGE-SORT(左边) 5
            →MERGE-SORT(左边) p>=r 返回
        →MERGE-SORT(右边) 2
            →MERGE-SORT(左边) p>=r 返回
        →MERGE 2 5//A:2 5 4 7 1 3 2 6
    →MERGE-SORT(右边) 4   7
        →MERGE-SORT(左边) 4
            →MERGE-SORT(左边) p>=r 返回
        →MERGE-SORT(右边) 7
            →MERGE-SORT(左边) p>=r 返回
        →MERGE 4 7//A:2 5 4 7 1 3 2 6 返回
    →MERGE 2 4 5 7//A:2 4 5 7 1 3 2 6 返回
→MERGE-SORT(右边) 1   3   2   6
    →MERGE-SORT(左边) 1   3
        →MERGE-SORT(左边) 1
            →MERGE-SORT(左边) p>=r 返回
        →MERGE-SORT(右边) 3
            →MERGE-SORT(左边) p>=r 返回
        →MERGE 1 3//A:2 5 4 7 1 3 2 6 返回
    →MERGE-SORT(右边) 2   6
        →MERGE-SORT(左边) 2
            →MERGE-SORT(左边) p>=r 返回
        →MERGE-SORT(右边) 6
            →MERGE-SORT(左边) p>=r 返回
        →MERGE 2 6//A:2 5 4 7 1 3 2 6 返回
    →MERGE 1 2 3 6//A:2 5 4 7 1 2 3 6 返回
→MERGE 1 2 2 3 4 5 6 7//A:1 2 2 3 4 5 6 7 返回

---

下面的都是我自己写的不是标准答案！！！

---

1.说明归并排序在数组A=<3,41,52,26,38,57,9,49>上的操作

2.重写过程MERGE，使之不使用无穷∞,而是一旦数组L或R的所有元素均被复制回A就立即停止，然后把另一个数组的剩余部分复制回A

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]
i=1
j=1
for k=p to r
    if L[i]<=R[j]
        A[k]=L[i]
        i=i+1
    else
        A[k]=R[j]
        j=j+1
    if i == n1+1 or j == n2+1
        break
if i<n1+1
    for k to r
        A[k]=L[i]
        i=i+1
else
    for k to r
    A[k]=R[j]
    j=j+1