Mam posortowaną tablicę JavaScript i chcę wstawić jeszcze jeden element do tablicy, tak że powstała tablica pozostaje posortowana. Z pewnością mógłbym wdrożyć prostą funkcję wstawiania w stylu quicksort:

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));

[OSTRZEŻENIE] ten kod zawiera błąd podczas próby wstawienia na początek tablicy, np.insert(2, [3, 7 ,9]) powoduje błędy [3, 2, 7, 9].

Zauważyłem jednak, że implementacje funkcji Array.sort mogą potencjalnie to zrobić dla mnie i natywnie:

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));

Czy istnieje dobry powód, aby wybrać pierwszą implementację na drugą?

Edytować: Zauważ, że w przypadku ogólnym wstawienie O (log (n)) (jak zaimplementowano w pierwszym przykładzie) będzie szybsze niż ogólny algorytm sortowania; jednak niekoniecznie dotyczy to w szczególności JavaScript. Zauważ, że:

Najlepszym przypadkiem dla kilku algorytmów wstawiania jest O (n), które wciąż znacząco różni się od O (log (n)), ale nie jest tak złe jak O (n log (n)), jak wspomniano poniżej. Spowodowałoby to zastosowanie konkretnego algorytmu sortowania (patrzImplementacja JavaScript Array.sort?)Metoda sortowania w JavaScript jest funkcją natywną, więc potencjalnie osiągnięcie ogromnych korzyści - O (log (n)) z ogromnym współczynnikiem może nadal być znacznie gorsze niż O (n) dla rozsądnie dużych zbiorów danych.