新JavaScript例文辞典

配列内のデータをソートする(マージソート)

説明

ソート方法の1つにマージソートがあります。一度データを分解し、その後連結(マージ)していくことでソートを行います。JavaScriptで処理する場合は再帰が絡むのでローカル変数は必ずvarで宣言しないと再帰エラーが発生します。

サンプルプログラム

var data = new Array(30, 10, -5, 99, 44, 65, 10, 31, 1, -57, 88, 78);
buff = new Array();
function sortData(data,start,end){
if (start >= end) return;
var mid = Math.floor((start + end) / 2);
sortData(data,start,mid);
sortData(data,mid+1,end);
var p = 0;
for (var i=start; i<=mid; i++) buff[p++] = data[i];
i = mid + 1;
var j = 0;
var k = start;
while ((i<=end) && (j<p)) {
if (buff[j] <= data[i]) {
data[k++] = buff[j++];
}else{
data[k++] = data[i++];
}
}
while (j < p) data[k++] = buff[j++];
}
document.write("ソート前:"+data.toString()+"<br>");
sortData(data,0,data.length-1);
document.write("ソート後:"+data.toString()+"<br>");
サンプルを実行
[戻る]