Slowsort

Multiply and surrender.

Best O(n^log n) Avg O(n^log n) Worst O(n^log n) Space O(n) Stable No In-place Yes Comparison-based

How it works

Multiply and surrender.

Implementation

function slowSort(arr, stats) {
  function slow(i, j) {
    if (i >= j) return;
    const m = Math.floor((i + j) / 2);
    slow(i, m);
    slow(m + 1, j);
    compare(m, j);
    if (arr[j] < arr[m]) {
      [arr[j], arr[m]] = [arr[m], arr[j]];
      swap(m, j);
    }
    slow(i, j - 1);
  }
  if (arr.length > 1) slow(0, arr.length - 1);
}