edwardbeckett
10/12/2018 - 11:46 PM

## Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, now with more input validation and support for (non-astral-plane-safe) string sorti

Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, now with more input validation and support for (non-astral-plane-safe) string sorting (MIT License): https://web.archive.org/web/20151002230717/http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

``````// https://web.archive.org/web/20141119215047/http://jsperf.com/javascript-quicksort-comparisons
// based on work from Vladimir Yaroslavskiy: https://web.archive.org/web/20151002230717/http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
var dualPivotQuicksort = (function (Math, toString, undefined) {
'use strict';
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function dualPivotQuicksort(arr, comp, left, right, div) {
var len = right - left, i, j;
if (len < 27) { // insertion sort for tiny array
for (i = left + 1; i <= right; i++) for (j = i; j > left && comp(arr[j], arr[j - 1]) < 0; j--) swap(arr, j, j - 1);
return arr;
}
var third = Math.floor(len / div), //TODO: check if we need to round up or down or just nearest
m1 = left + third, m2 = right - third; // 'medians'
if (m1 <= left) m1 = left + 1;
if (m2 >= right) m2 = right - 1;
if (comp(arr[m1], arr[m2]) < 0) {
swap(arr, m1, left);
swap(arr, m2, right);
} else {
swap(arr, m1, right);
swap(arr, m2, left);
}
var pivot1 = arr[left], pivot2 = arr[right], // pivots
less  = left  + 1, great = right - 1; // pointers
for (i = less; i <= great; i++) { // sorting
if (comp(arr[i], pivot1) < 0) swap(arr, i, less++);
else if (comp(arr[i], pivot2) > 0) {
while (i < great && comp(arr[great], pivot2) > 0) great--;
swap(arr, i, great--);
if (comp(arr[i], pivot1) < 0) swap(arr, i, less++);
}
}
var dist = great - less; // swaps
if (dist < 13) div++;
swap(arr, less  - 1, left);
swap(arr, great + 1, right);
dualPivotQuicksort(arr, comp, left,   less - 2, div); // subarrays
dualPivotQuicksort(arr, comp, great + 2, right, div);
if (dist > len - 13 && pivot1 !== pivot2) { // equal elements
for (i = less; i <= great; i++) {
if (arr[i] === pivot1) swap(arr, i, less++);
else if (arr[i] === pivot2) {
swap(arr, i, great--);
if (arr[i] === pivot1) swap(arr, i, less++);
}
}
}
if (comp(pivot1, pivot2) < 0) return dualPivotQuicksort(arr, comp, less, great, div); // subarray
return arr;
}
function compare(a, b) {
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
function sort(array, comparison, fromIndex, toIndex) { // not astral-plane safe
var isStr = typeof array === 'string' || toString.call(array) === '[object String]',
arr = isStr ? array.split('') : array, len = arr.length || 0,
comp = typeof comparison === 'function' ? comparison : compare,
fromIdx = (typeof fromIndex === 'symbol' || toString.call(fromIndex) === '[object Symbol]') ?
0 : Math.min(fromIndex || 0, len) || 0,
toIdx = (typeof toIndex === 'symbol' || toString.call(toIndex) === '[object Symbol]') ?
0 : Math.min(toIndex || len, len);
if (toIdx !== toIdx) toIdx = len; // check against NaN
if (fromIdx < 0) fromIdx = Math.max(0, len + fromIdx); // support negative indexes
if (toIdx < 0) toIdx = Math.max(0, len + toIdx);
if (fromIdx < toIdx) dualPivotQuicksort(arr, comp, fromIdx, toIdx - 1, 3);
else if (toIdx < fromIdx) dualPivotQuicksort(arr, comp, toIdx, fromIdx - 1, 3);
else return array;
return isStr ? arr.join('') : arr;
}
sort.sort = sort;
return sort;
})(Math, Object.prototype.toString);``````