(JavaScript)安定なソートを実装する

作ったもの

Javascriptの仕様によると、sort()は、元の配列の前後関係を保障しない不安定なソートだそうです。
安定なソートも欲しいので、実装してみました。

コード

function msort(ary){
	let len = ary.length;
	let block = 8; // ソート済ブロックの大きさ
	for(let i = 0; i < len; i += block){
		// 少ない要素の比較なら、挿入ソートが速い
		let done = 1;
		let end = Math.min(i + block, len);
		let a = i + 1;
		while(a < end){
			while(a > i){
				if(ary[a-1] > ary[a]){
					let t = ary[a-1]; ary[a-1] = ary[a]; ary[a] = t;
					a--;
				}else{break;}
			}
			done++;
			a = i + done;
		}
	}
	if(block >= len){return;}
	let buff = new Array(len);
	let src = ary;
	let dst = buff;
	let srcIsAry = true;
	while(block < len){
		for(let i = 0; i < len;){
			let beg = i;
			let mid = Math.min(i + block, len);
			let end = Math.min(mid + block, len);
			for(let a = beg, b = mid; i < end; i++){
				if(a === mid){
					dst[i] = src[b];
					b++;
					continue;
				}else if(b === end){
					dst[i] = src[a];
					a++;
					continue;
				}
				if(src[a] > src[b]){
					dst[i] = src[b];
					b++;
				}else{
					dst[i] = src[a];
					a++;
				}
			}
		}
		block *= 2;
		let tmp = src; src = dst; dst = tmp;
		srcIsAry = !srcIsAry; // srcとdstを入れ替えながら処理する
	}
	if(!srcIsAry){ // src が 元データならコピー処理をスキップ
		for(let i = len; i-->0;){
			dst[i] = src[i];
		}
	}
}

補足

アルゴリズムは、安定ソートの代表のマージソートを使用しました。小さな要素数（≦１０）のデータをソートする際には、挿入ソートの方が速いようなので、途中までは挿入ソートを使い、途中からマージソートに切り替えます。

10万要素のソートを行った場合
標準ソート：50ms
自作ソート：120ms
となり、２倍ほど遅いですが、実用上は許容範囲かと。（実行環境はGoogle Chrome）