Я заметил, что функция сортировки Javascript чрезвычайно медленная в версиях Internet Explorer ниже 9 (часто на порядок по сравнению с Firefox и другими. Я реализую свою собственную версию, чтобы посмотреть, смогу ли я добиться большего успеха.Сортировка слиянием работает прилично, но кажется, что большая часть документации для алгоритмов сортировки предполагает, что массивы реализованы как непрерывные блоки памяти. Массивы Javascript реализованы как объекты (по крайней мере, в старых браузерах).
Мне было интересноЕсть ли алгоритм сортировки, который учитывает тот факт, что доступ к массиву является более дорогим, чем обычно? То есть тот, который пытается оптимизировать не только количество сравнений, но также число обращений и стоимость создания новых массивов с помощьютакие вещи, как splice и slice. Вот моя попытка сортировки слиянием.
function mergeSort(array, compareFunc) {
if (array.length <= 1) {
return;
}
var mid = Math.floor(array.length/2);
var left = array.splice(0, mid);
var right = array.splice(0, array.length);
mergeSort(left, compareFunc);
mergeSort(right, compareFunc);
while ((left.length > 0) && (right.length > 0))
{
if (compareFunc(left[0], right[0]) <= 0) {
array.push(left.shift());
}
else {
array.push(right.shift());
}
}
while (left.length > 0) {
array.push(left.shift());
}
while (right.length > 0) {
array.push(right.shift());
}
return;
}