Sort Algorithm Race

const N = 80;
const OPS_PER_FRAME = 40;
let racers;
let restartAt = 0;

function shuffle(a) {
  for (let i = a.length - 1; i > 0; i--) {
    const j = (Math.random() * (i + 1)) | 0;
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}
function baseArr() {
  const a = [];
  for (let i = 0; i < N; i++) a.push(i + 1);
  return shuffle(a);
}

function* bubbleGen(a) {
  let n = a.length;
  let swapped = true;
  while (swapped) {
    swapped = false;
    for (let i = 1; i < n; i++) {
      yield { hl: [i - 1, i] };
      if (a[i - 1] > a[i]) { [a[i - 1], a[i]] = [a[i], a[i - 1]]; swapped = true; }
    }
    n--;
  }
}
function* insertionGen(a) {
  for (let i = 1; i < a.length; i++) {
    let j = i;
    while (j > 0) {
      yield { hl: [j - 1, j] };
      if (a[j - 1] > a[j]) { [a[j - 1], a[j]] = [a[j], a[j - 1]]; j--; }
      else break;
    }
  }
}
function* mergeGen(a) {
  const aux = a.slice();
  function* ms(lo, hi) {
    if (hi - lo <= 1) return;
    const mid = (lo + hi) >> 1;
    yield* ms(lo, mid);
    yield* ms(mid, hi);
    for (let k = lo; k < hi; k++) aux[k] = a[k];
    let i = lo, j = mid;
    for (let k = lo; k < hi; k++) {
      yield { hl: [i < mid ? i : mid - 1, j < hi ? j : hi - 1] };
      if (i >= mid) a[k] = aux[j++];
      else if (j >= hi) a[k] = aux[i++];
      else if (aux[i] <= aux[j]) a[k] = aux[i++];
      else a[k] = aux[j++];
    }
  }
  yield* ms(0, a.length);
}
function* quickGen(a) {
  function* qs(lo, hi) {
    if (lo >= hi) return;
    const piv = a[hi];
    let i = lo;
    for (let j = lo; j < hi; j++) {
      yield { hl: [j, hi] };
      if (a[j] < piv) { [a[i], a[j]] = [a[j], a[i]]; i++; }
    }
    [a[i], a[hi]] = [a[hi], a[i]];
    yield { hl: [i, hi] };
    yield* qs(lo, i - 1);
    yield* qs(i + 1, hi);
  }
  yield* qs(0, a.length - 1);
}

const palettes = [
  { bg: "#2a1414", bar: "#ff7755", name: "Bubble" },
  { bg: "#14241a", bar: "#66dd88", name: "Insertion" },
  { bg: "#141a2a", bar: "#6699ff", name: "Merge" },
  { bg: "#241a14", bar: "#ffcc55", name: "Quick" },
];

function reset() {
  const base = baseArr();
  const factories = [bubbleGen, insertionGen, mergeGen, quickGen];
  racers = factories.map((f, k) => {
    const arr = base.slice();
    return { arr, gen: f(arr), done: false, ops: 0, hl: [-1, -1], pal: palettes[k] };
  });
  restartAt = 0;
}

function init() { reset(); }

function drawQuad(ctx, r, x, y, w, h) {
  ctx.fillStyle = r.pal.bg;
  ctx.fillRect(x, y, w, h);
  const pad = 4;
  const bw = (w - pad * 2) / N;
  const maxH = h - 28;
  for (let i = 0; i < N; i++) {
    const v = r.arr[i];
    const bh = (v / N) * maxH;
    const bx = x + pad + i * bw;
    const by = y + h - bh - 4;
    const flash = i === r.hl[0] || i === r.hl[1];
    ctx.fillStyle = flash ? "#ffffff" : r.pal.bar;
    ctx.fillRect(bx, by, Math.max(1, bw - 1), bh);
  }
  ctx.fillStyle = "#fff";
  ctx.font = "12px monospace";
  ctx.fillText(r.pal.name, x + 8, y + 16);
  ctx.fillStyle = "#ddd";
  ctx.fillText("ops " + r.ops + (r.done ? " ✓" : ""), x + 8, y + h - 8);
}

function tick({ ctx, width: W, height: H }) {
  for (const r of racers) {
    if (r.done) continue;
    let n = OPS_PER_FRAME;
    while (n-- > 0) {
      const nx = r.gen.next();
      if (nx.done) { r.done = true; r.hl = [-1, -1]; break; }
      r.ops++;
      r.hl = nx.value.hl;
    }
  }
  ctx.fillStyle = "#0a0a0a";
  ctx.fillRect(0, 0, W, H);
  const hw = W / 2, hh = H / 2;
  drawQuad(ctx, racers[0], 0, 0, hw, hh);
  drawQuad(ctx, racers[1], hw, 0, hw, hh);
  drawQuad(ctx, racers[2], 0, hh, hw, hh);
  drawQuad(ctx, racers[3], hw, hh, hw, hh);
  ctx.strokeStyle = "#000";
  ctx.lineWidth = 2;
  ctx.beginPath();
  ctx.moveTo(hw, 0); ctx.lineTo(hw, H);
  ctx.moveTo(0, hh); ctx.lineTo(W, hh);
  ctx.stroke();

  if (racers.every((r) => r.done)) {
    if (!restartAt) restartAt = performance.now() + 1200;
    else if (performance.now() >= restartAt) reset();
  }
}