合併排序(Merge sort)是建立在合併操作之上的一種高效排序演算法,也是分治法(Divide and Conquer)最典型的應用之一。
它的核心思路是把待排序序列拆成若干子序列,讓每個子序列各自有序,再將這些有序子序列合併成整體有序的序列。將兩個有序表合併成一個有序表,稱為 2-路歸並。
合併操作的步驟:
示例一:
function mergeSort(items) {
if (items.length < 2) {
return items;
}
var middle = Math.floor(items.length / 2),
left = items.slice(0, middle),
right = items.slice(middle),
params = merge(mergeSort(left), mergeSort(right));
params.unshift(0, items.length);
items.splice.apply(items, params);
return items;
function merge(left, right) {
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
return result.concat(left.slice(il)).concat(right.slice(ir));
}
}
// test
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
mergeSort(arr);
示例二:
<script type="text/javascript">
var count = 0;
// source 為來源陣列,dest 為目標陣列,s 為起始下標,t 為結束下標
function mSort(source, dest, s, t) {
var result = "";
var m;
var dest2 = new Array();
if (s == t) {
dest[s] = source[s];
} else {
m = Math.floor((s + t) / 2);
mSort(source, dest2, s, m);
mSort(source, dest2, m + 1, t);
merge(dest2, dest, s, m, t);
result += "<br />第" + ++count + "遍排序的結果是:";
for (var n = 0; n < dest.length; n++) {
result += array[n] + ",";
}
}
return result;
}
// 將兩個陣列依從小到大合併
function merge(source, dest, s, m, n) {
for (var j = m + 1, k = s; j <= n && s <= m; k++) {
if (source[s] < source[j]) {
dest[k] = source[s++];
} else {
dest[k] = source[j++];
}
}
// 將剩餘的有序元素補到 dest 末端
if (s <= m) {
for (var l = 0; l <= m - s; l++) {
dest[k + l] = source[s + l];
}
}
if (j <= n) {
for (var l = 0; l <= n - j; l++) {
dest[k + l] = source[j + l];
}
}
}
</script>