Fast Sorting in JavaScript / zansh.in

2 min read

Fast Sorting in JavaScript

It's somewhat taboo these days to mess with native prototypes, but there's a wonderful trick from times gone by that exploits the fact that Array.prototype.sort() uses Object.prototype.toString() internally if you don't specify a sort-function.

Take this usual example:

let data = [{ key: 'b' }, { key: 'c' }, { key: 'a' }]

data.sort((a, b) => a.key.localeCompare(b.key))
// [{ key: 'a' }, { key: 'b' }, { key: 'c' }];

Let's temporarily rewrite Object.prototype.toString():

let data = [{ key: 'b' }, { key: 'c' }, { key: 'a' }]

function hackSort(array, toStringFn) {
  const _toString = Object.prototype.toString

  Object.prototype.toString = toStringFn
  array.sort()
  Object.prototype.toString = _toString

  return array
}

hackSort(data, function () {
  // This has to be a regular
  // function, not an arrow.
  // Otherwise we can't access
  // 'this'.
  return this.key
})
// [{ key: 'a' }, { key: 'b' }, { key: 'c' }];

I've used and abused this technique many times for large data-sets with significant performance increases on non-Chrome browsers.

Yes, despite the age of the aforementioned article this technique still doesn't work in Chrome. Fortunately, it's also possible to detect if the optimisation is possible:

const hackSortIsFast = (function () {
  let array = [{}, {}, {}]

  // Rewrite #toString to count
  // how often it's called
  let count = 0
  const _toString = Object.prototype.toString
  Object.prototype.toString = function () {
    count += 1
    return ''
  }
  array.sort()
  Object.prototype.toString = _toString

  // 3 is O(n), more will be O(n log n)
  return count === 3
})()
// false on Chrome, true on
// Safari and Firefox

Since we can't access the two elements being compared with this technique, sorting integers must be done with something like String.prototype.padStart():

let data = [{ key: 10 }, { key: 2 }, { key: 1 }]
const MAX_INT_LENGTH = String(Number.MAX_SAFE_INTEGER).length

hackSort(data, function () {
  return String(this.key).padStart(MAX_INT_LENGTH, '0')
})
// [{ key: 1 }, { key: 2 }, { key: 10 }];

Notice that integers will remain integers. They will not be converted to strings. #toString is only used for comparison, and the array elements themselves will not be mutated.

Mind you, at this point things are starting to get a little out-of-hand!

31 Aug, 2022