This implicitly assumes that Array.sort is stable: that is, if the comparison function returns 0 then sorting leaves the array elements in their original relati

This implicitly assumes that Array.sort is stable: that is, if the comparison function returns 0 then sorting leaves the array elements in their original relative positions. That's not guaranteed by the JavaScript specification, see e.g. https://bugs.chromium.org/p/v8/issues/detail?id=90 https://bugs.chromium.org/p/v8/issues/detail?id=90 It just so happens that in V8, the built-in sort uses an unstable quicksort for large arrays but a stable insertion sort for small ones, so the rest of your analysis is correct.