testing performance of sorting with or without pre-sorting

test_sorting.js

#!/usr/bin/env node

// Environment
// ------------------
// NodeJS: v12.14.0
// CPU: 2.50GHz
// arrays length = 1000 (that is, sorting 1000^2 elements)

// Results
// ------------------
// sort all elements at once: 339.207ms
// sort all elements at once: 13897983 ops
// --
// pre-sort elements within arrays: 200.371ms
// pre-sort elements within arrays: 8634082 ops
// --
// sort all elements after concatenating pre-sorted arrays: 145.794ms
// sort all elements after concatenating pre-sorted arrays: 6240126 ops
// --
// saved operations if pre-sorting isnt cached = -976225 (-7%)
// saved operations if pre-sorting is cached (and thus considered free) = 7657857 (55%)

// Conclusion
// ------------------
// Pre-sorting seems to work well with V8 implementation of the TimSort algorithm, which
// "finds subsequences of the data that are already ordered and uses them to sort the remainder more efficiently"
// Source: https://en.wikipedia.org/wiki/Timsort
// See also: https://github.com/nodejs/node/pull/22754#issuecomment-419551068


const length = 1000
const max = 1000

// Generating an array of ${length} length, made of arrays of ${length} length,
// made of random number between 0 and ${max}
let arrayOfArrays = []
let i = 0
while (i < length) {
  arrayOfArrays[i] = []
  let j = 0
  while (j < length) {
    arrayOfArrays[i][j] = Math.trunc(Math.random() * max)
    j++
  }
  i++
}

let opsCount = 0
const sortArray = array => array.sort(ascending)
const ascending = (a, b) => {
  ++opsCount
  return a - b
}

console.time('sort all elements at once')
sortArray([].concat(...arrayOfArrays))
console.timeEnd('sort all elements at once')
const a = opsCount
console.log(`sort all elements at once: ${opsCount} ops`)

console.log('--')

opsCount = 0
console.time('pre-sort elements within arrays')
const sortedArrays = arrayOfArrays.map(sortArray)
console.timeEnd('pre-sort elements within arrays')
const b = opsCount
console.log(`pre-sort elements within arrays: ${opsCount} ops`)

console.log('--')

// Reset counter
opsCount = 0
console.time('sort all elements after concatenating pre-sorted arrays')
sortArray([].concat(...sortedArrays))
console.timeEnd('sort all elements after concatenating pre-sorted arrays')
const c = opsCount
console.log(`sort all elements after concatenating pre-sorted arrays: ${opsCount} ops`)

console.log('--')

console.log(`saved operations if pre-sorting isnt cached = ${a - (b+c)} (${100 - Math.round(100 * (b+c)/a)}%)`)
console.log(`saved operations if pre-sorting is cached (and thus considered free) = ${a - c} (${100 - Math.round(100 * c/a)}%)`)