[解決済み] ソートされた数値の配列に数値を挿入する効率的な方法？

質問

ソートされたJavaScriptの配列があり、その配列にもう1つアイテムを挿入して、結果の配列をソートしたままにしたい。 私は確かに単純なクイックソートスタイルの挿入関数を実装することができました。

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

警告 このコードには、配列の先頭に挿入しようとしたときに発生するバグがあります。 insert(2, [3, 7 ,9] ) は、正しくない [ 3, 2, 7, 9 ] を生成します。

しかし、Array.sort関数の実装が、私のために、そしてネイティブに、これを行う可能性があることに気づきました。

var array = [1,2,3,4,5,6,7,8,9];
var element = 3.5;
function insert(element, array) {
  array.push(element);
  array.sort(function(a, b) {
    return a - b;
  });
  return array;
}

console.log(insert(element, array));

2番目の実装ではなく、1番目の実装を選択する正当な理由はあるのでしょうか？

編集 : 一般的なケースでは、O(log(n))挿入(最初の例で実装)は一般的なソートアルゴリズムより高速であることに注意してください。しかし、これは特にJavaScriptでは必ずしもそうとは限りません。そのことに注意してください。

• いくつかの挿入アルゴリズムのベストケースは O(n) で、これはまだ O(log(n)) とは大きく異なりますが、以下に述べる O(n log(n)) ほどではありません。 これは、使用される特定のソートアルゴリズムに起因するものでしょう ( JavascriptのArray.sortの実装は？ )
• JavaScript の sort メソッドはネイティブ関数であり、潜在的に大きな利点を実現します -- 巨大な係数を持つ O(log(n)) は、適度な大きさのデータセットでは O(n) よりはるかに悪い場合もあります。

どのように解決するのか？

Windows 7 の Chrome を使って、10万個のソート済み数値の配列に1000個のランダムな要素を挿入する方法を試してみたところ、1つのデータが得られました。

First Method:
~54 milliseconds
Second Method:
~57 seconds

つまり、少なくともこの設定においては、ネイティブメソッドでは補えないのです。 これは、1000の配列に100の要素を挿入するような小さなデータセットでも同様です。

First Method:
1 milliseconds
Second Method:
34 milliseconds