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 = [];
var a = p, b = q + 1, k = p;
while(a <= q && b <= r) {
if(arr[a] <= arr[b]) {
crr.push(arr[a]);
a ++;
} else {
crr.push(arr[b]);
b ++;
}
k ++;
}
if(a === q + 1) {
while(b <= r) {
crr.push(arr[b]);
b ++;
}
} else {
while(a <= q) {
crr.push(arr[a]);
a ++;
}
}
var i = 0, cl = crr.length;
while(i < cl) {
arr[p++] = crr[i++];
}
return arr;
}
function mergesort(arr, low, high) {
if(low === high) {
return arr;
} else if(high – low === 1) {
if(arr[low] > arr[high]) {
var temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
return arr;
} else {
var mid = parseInt((low+high)/2);
arr = mergesort(arr, low, mid);
arr = mergesort(arr, mid+1, high);
return merge(arr, low, mid, high);
}
}
// 示例
var test = [88, 32, 22, 32, 87, 88];
console.log(mergesort(test, 0, test.length – 1));