（思いついたら追加していこうかと）

経緯

キャンペーンとのことで参加してみようと
https://qiita.com/official-campaigns/engineer-festa/2022

お題を探してたところ、こちらのソートアルゴリズムの記事を拝見し、
https://qiita.com/fuwasegu/items/0f27a7eee2ec72035855
いっちょあたくしも考えてみっか、と思い立ちまして。

javascript で並べ替えと言えばこれです。

sort.js

source.sort((a, b) => a - b);

ということで、javascript エンジンはどれも、これが最速になるよう実装してそうです。（たぶん）
よって勝つのは難しそうですが、どこまで迫れるか、考えてみます。

条件

・javascript で実装
・Windows 10 Home 21H2 19044.1766 （64 ビット）
・Chrome 103.0.5060.66（Official Build）（64 ビット）
　DevTools の Console にコードを貼り付けて実行
・対象配列は下記4パターン

sourceArray.js

// 1.乱数の範囲：0～8,191、要素数：1万
const source = [...Array(10**4)].map(_ => Math.floor(Math.random()*8192));

// 2.乱数の範囲：0～8,191、要素数：10万
const source = [...Array(10**5)].map(_ => Math.floor(Math.random()*8192));

// 3.乱数の範囲：0～65,535、要素数：10万
const source = [...Array(10**5)].map(_ => Math.floor(Math.random()*65536));

// 4.乱数の範囲：0～65,535、要素数：100万
const source = [...Array(10**6)].map(_ => Math.floor(Math.random()*65536));

結果

※値はミリ秒で、上位3桁に四捨五入

アルゴリズム	配列1	配列2	配列3	配列4	感想
sort((a, b) => a - b)	4.54	48.4	52.6	488	早い上に安定してるさすが
Min Max 法	92.0	7,820	8,230	-	全然相手にならないですね
Min Max+ 法	18.7	1,250	1,300	-	かなり改善もまだ桁が違うさらに案が必要そう
Min Max++ 法	14.6	182	219	6,830	MinMax+からさらに改善あともう一歩
Value Index 法	6.41	35.2	69.2	409	え？超えた？

各案の詳細

以下の案すべて、勝手ネーミングです。

1. Min Max 法

配列から最大値と最小値を探し、
それを結果配列に追加しつつ、元配列から削除、
これを繰り返します。

minMaxSort.js

const high = [];
const low = [];
while(source.length > 1) {
	let max = {value: source[0], index: 0};
	let min = {value: source[0], index: 0};
	for (let i = 1; i < source.length; i++) {
		if (max.value < source[i]) {
			max.value = source[i];
			max.index = i;
		}
		else if (source[i] < min.value) {
			min.value = source[i];
			min.index = i;
		}
	}
	high.unshift(max.value);
	low.push(min.value);
	if (min.index < max.index) {
		source.splice(max.index, 1);	
		source.splice(min.index, 1);		
	}
	else {
		source.splice(min.index, 1);		
		source.splice(max.index, 1);
	}
}
if (source.length) low.push(source[0]);
const result = [...low, ...high];

2. Min Max+ 法

配列の要素を先頭から順に、都度、
・これまでで最大であれば結果配列の末尾に追加
・これまでで最小であれば結果配列の先頭に追加
・最大でも最小でもない場合は、
　最大値と最小値との差の小さい方から順に
　結果配列と比較していき追加すべき index を探します。

minMaxPlusSort.js

const result = [source.shift()];
source.forEach(s => {
	if (result[result.length - 1] <= s) {
		result.push(s);
	}
	else if (s <= result[0]) {
		result.unshift(s);
	}
	else if ((s - result[0]) < (result[result.length - 1] - s)) {
		for (let j = 1; j < result.length; j++) {
			if (s <= result[j]) {
				result.splice(j, 0, s);
				break;
			}
		}
	}
	else {
		for (let j = result.length - 2; 0 <= j; j--) {
			if (result[j] <= s) {
				result.splice(j + 1, 0, s);
				break;
			}
		}
	}
}

3. Min Max++ 法

Min Max+ 法で、最大でも最小でもない場合を置き換えたものです。
最大でも最小でもない場合は、「別の配列」を用意しそこに格納し、
その「別の配列」においても、都度、
・これまでで最大であれば「別の配列」の末尾に追加
・これまでで最小であれば「別の配列」の先頭に追加
・最大でも最小でもない場合は、「さらに別の配列」を用意しそこに格納
これを最後まで繰り返します。

値の格納された各配列はソート済になるので
各配列の先頭を比較し、最小のものを削除しては結果配列の末尾に追加、
これを最後まで繰り返すとできあがりです。

minMaxPlusPlusSort.js

const temp = [[source.shift()]];
source.forEach(s => {
	let added = false;
	for (let i = 0; i < temp.length; i++) {
		if (temp[i][temp[i].length - 1] <= s) {
			temp[i].push(s);
			added = true;
			break;
		}
		else if (s <= temp[i][0]) {
			temp[i].unshift(s);
			added = true;
			break;
		}
	}
	if (!added) temp.push([s]);
});
const result = [temp[0].shift()];
while (temp.length) {
	let min = {value: temp[0][0], index: 0};
	for (let i = 1; i < temp.length; i++) {
		if (temp[i][0] < min.value) {
			min = {value: temp[i][0], index: i};
		}
	}
	result.push(temp[min.index].shift());
	if (!temp[min.index].length) temp.splice(min.index, 1);
}

4. Value Index 法

ソートアルゴリズムが for (let i = ... を含まないってあり得るんでしょうか。
この案では出てこないです。
まあ、sort() を使わずソートできてるのでよしとしましょうか。
一応、これが現在の自己ベストです。

数値をそのまま結果配列のインデックスにします。
ただ、同値が上書きされていくと、結果配列の要素数が足りなくなるため
結果配列の要素は値ではなく配列にし、値はその要素配列（2次元目の配列）に追加します。

valueIndexSort.js

let result = [];
source.forEach(v => result[v]
                    ? result[v].push(v)
                    : result[v] = [v]);
result = result.filter(v => v)
               .flat();

※これ、最大値(M)に対して要素数(n)が十分に大きい場合に早くなるようです
　ここ、n/M = ? とかで境界が表せるのか確認したいと思います

全コード

タイマと検算を含む全コードです。
Chrome DevTools Console に貼付 Enter でチェックできます。
（MinMax は遅いのでコメントにしています）

all.js

const source = new class {
	constructor() {
		//this.source = [...Array(10**4)].map(_ => Math.floor(Math.random()*8192));
		  this.source = [...Array(10**5)].map(_ => Math.floor(Math.random()*8192));
		//this.source = [...Array(10**5)].map(_ => Math.floor(Math.random()*65536));
		//this.source = [...Array(10**6)].map(_ => Math.floor(Math.random()*65536));
	}
	get() {
		return JSON.parse(JSON.stringify(this.source));	//deep copy
	}
}();
const defaultSort = new class DefaultSort {
	constructor() {
		this.result = [];
		console.time(DefaultSort.name);
		this.do();
		console.timeEnd(DefaultSort.name);
	}
	do() {
		this.result = source.get().sort((a, b) => a - b);
	}
	validate(name, arr) {
		const isCorrect = this.result.length === arr.length
						&& !this.result.some((s, i) => s !== arr[i]);
		console.assert(isCorrect, name + ' incorrect');		
	}
}();
/*
const _mm = new class MinMax {
	constructor() {
		this.result = [];
		console.time(MinMax.name);
		this.do();
		console.timeEnd(MinMax.name);
		defaultSort.validate(MinMax.name, this.result);
	}
	do() {
		const s = source.get();
		const high = [];
		const low = [];
		while(s.length > 1) {
			let max = {value: s[0], index: 0};
			let min = {value: s[0], index: 0};
			for (let i = 1; i < s.length; i++) {
				if (max.value < s[i]) {
					max = {value: s[i], index: i};
				}
				else if (s[i] < min.value) {
					min = {value: s[i], index: i};
				}
			}
			high.unshift(max.value);
			low.push(min.value);
			if (min.index < max.index) {
				s.splice(max.index, 1);	
				s.splice(min.index, 1);		
			}
			else {
				s.splice(min.index, 1);		
				s.splice(max.index, 1);
			}
		}
		if (s.length) low.push(s[0]);
		this.result = [...low, ...high];	
	}
}();
*/
const _mmp = new class MinMaxPlus {
	constructor() {
		this.result = [];
		console.time(MinMaxPlus.name);
		this.do();
		console.timeEnd(MinMaxPlus.name);
		defaultSort.validate(MinMaxPlus.name, this.result);
	}
	do() {
		const _source = source.get();
		const result = [_source.shift()];
		_source.forEach(s => {
			if (result[result.length - 1] <= s) {
				result.push(s);
			}
			else if (s <= result[0]) {
				result.unshift(s);
			}
			else if ((s - result[0]) < (result[result.length - 1] - s)) {
				for (let j = 1; j < result.length; j++) {
					if (s <= result[j]) {
						result.splice(j, 0, s);
						break;
					}
				}
			}
			else {
				for (let j = result.length - 2; 0 <= j; j--) {
					if (result[j] <= s) {
						result.splice(j + 1, 0, s);
						break;
					}
				}
			}
		});
		this.result = result;
	}
}();
const _mmpp = new class MinMaxPlusPlus {
	constructor() {
		this.result = [];
		console.time(MinMaxPlusPlus.name);
		this.do();
		console.timeEnd(MinMaxPlusPlus.name);
		defaultSort.validate(MinMaxPlusPlus.name, this.result);
	}
	do() {
		const _source = source.get();
		const temp = [[_source.shift()]];
		_source.forEach(s => {
			let added = false;
			for (let i = 0; i < temp.length; i++) {
				if (temp[i][temp[i].length - 1] <= s) {
					temp[i].push(s);
					added = true;
					break;
				}
				else if (s <= temp[i][0]) {
					temp[i].unshift(s);
					added = true;
					break;
				}
			}
			if (!added) temp.push([s]);
		});
		const result = [temp[0].shift()];
		while (temp.length) {
			let min = {value: temp[0][0], index: 0};
			for (let i = 1; i < temp.length; i++) {
				if (temp[i][0] < min.value) {
					min = {value: temp[i][0], index: i};
				}
			}
			result.push(temp[min.index].shift());
			if (!temp[min.index].length) temp.splice(min.index, 1);
		}
		this.result = result;
	}
}();

const _vi = new class ValueIndex {
	constructor() {
		this.result = [];
		console.time(ValueIndex.name);
		this.do();
		console.timeEnd(ValueIndex.name);
		defaultSort.validate(ValueIndex.name, this.result);
	}
	do() {
		const result = [];
		source.get().forEach(v => result[v]
								? result[v].push(v)
								: result[v] = [v]);
		this.result = result.filter(v => v).flat();	
	}
}();

javascript: array.sort((a, b) => a - b) にどこまで迫れるか

経緯

条件

結果