Cacher is the code snippet organizer for pro developers

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