作者:zhanhailiang 日期:2012-12-17

1.首先需要引入合并两个已排序的表的算法 假设有一个数组A[1…m]，p,q,r为它的三个索引，并有1?p?q<r?m。两子数组A[p…q]，A[q+1…r]各按升序排列，我们需要重新安排A中的元素的位置，使得子数组A[p…r]也按升序排列。这就是合并A[p…q]和A[q+1…r]的过程。合并算法是如下工作，使用两个指针s和t，初始化时分别指向A[p]和A[q+1]，再用空数组B[p…r]做暂存器。每一次比较元素A[s]和A[t]，将小的元素添加到B，若相同则把A[s]添加进去。然后更新指针，若A[s]?A[t]，则s++；反之则t++，当条件s=q+1或t=r+1成立时结束。在第一种情况下将数组A[t…r]中剩余的元素添加到B，而另一种情况则将数组A[s…q]中剩余的元素添加到B。最后把数组B[p…r]复制加A[p…r]。如下给出伪代码：

/*****************************************************************************
算法：merge
输入：数组A[1...m]，p,q,r为它的三个索引，并有1<=p<=q<r<=m。两子数组A[p...q]，A[q+1...r]各按升序排列
输出：合并两个子数组A[p...q]，A[q+1...r]的新数组A[1...m]
******************************************************************************/

s = p; t = q + 1; k = p;
while(s <= q && t <= r) {
    if(A[s] <= A[t]) {
        B[k] = A[s];
        s++;
    } else {
        B[k] = A[t];
        t++;
    }
    k++;
}
if(s === q + 1) {
    B[k...r] = A[t...r];
} else {
    B[k...r] = A[s...q];
}
A[p...r] = B[p...r];

2.合并排序

/*****************************************************************************
算法：mergesort
输入：A[1...n]
输出：按非降序排列的数组A[1...n]
    mergesort(A, 1, n);
******************************************************************************/
过程 mergesort(A, low, high)
    if(low < high) {
        mid = parseInt((low + high) / 2);
        mergesort(A, low, mid);
        mergesort(A, mid + 1, high);
        merge(A, low, mid, high);
    }

按上述合并排序的伪代码给出合并排序的 JS实现版本：

function merge(arr, p, q, r) {
    var crr = [