ズルをして、「とても長い配列の上位M件だけをクイックソートより高速に取り出す」

とても長い配列の上位M件だけをクイックソートより高速に取り出すの計測用コードを見て、ズルをしたら微妙に早くなるんじゃないかと思って試したら３倍くらい早くなりました。

なお、ズルなので実用的ではありません。

計測結果

60回平均で３倍速。

test: 1
test: 2
...
test: 59
test: 60
QuickTopSort: 18.2989166666521ms
   CheatSort: 5.20891666669243ms

ズルの内容

入力データが一様分布であることから上位M件とそれ以外の下位を分離する値を大まかに予想し、最初のピポッドに使っています。

実装

元のquickTopSortのコードをコピペして次のように変えました。

修正済：なお、元のコードの if (from + 1 >= to) return; は if (from >= to) return; が正しいのではないかと思われます（quickSort([2,1])を実行してみる限り）。

function cheatSort(arr, M, p) {
  arr = arr.slice(0);
  cheatSortCore(arr, M, p);
  return arr;
}

function cheatSortCore(arr, M, p) {
  var i = 0,
      j = arr.length - 1,
      tmp;

  if (arr.length < 2) return arr;

  while (true) {
    while (arr[i] <  p && i <= j) i++;
    while (arr[j] >= p && i <= j) j--;

    if (i >= j) {break;}
    else {
      tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
  }

  quickTopSortCore(arr, M, 0, i - 1);
  if (i - 1 < M) quickTopSortCore(arr, M, i, arr.length - 1);
}

function test3() {
  var a = 0,
      b = 1e9,
      p = 2 * M * (b - a) / N + a;
  res3 = cheatSort(arr, M, p);
}