script.js

/* ============================================================
   Sorting Algorithm Lab v7
   Vanilla JS — no frameworks
   ============================================================ */

const ALGORITHM_IDS = [
  "bubble", "selection", "insertion", "merge", "quick", "heap", "shell", "radix",
  "counting", "cocktail", "comb", "gnome", "oddeven", "pancake", "cycle", "timsort",
];

// ---------- Algorithm metadata ----------
const ALGORITHM_PROFILES = {
  bubble: {
    name: "Bubble Sort",
    best: "O(n)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: true,
    inPlace: true,
    memory: "O(1)",
    description: "Repeatedly swaps adjacent out-of-order pairs until sorted.",
  },
  selection: {
    name: "Selection Sort",
    best: "O(n²)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: false,
    inPlace: true,
    memory: "O(1)",
    description: "Finds the minimum in the unsorted region and swaps it to the front.",
  },
  insertion: {
    name: "Insertion Sort",
    best: "O(n)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: true,
    inPlace: true,
    memory: "O(1)",
    description: "Builds a sorted prefix by inserting each element into place.",
  },
  merge: {
    name: "Merge Sort",
    best: "O(n log n)",
    avg: "O(n log n)",
    worst: "O(n log n)",
    stable: true,
    inPlace: false,
    memory: "O(n)",
    description: "Divide-and-conquer merge of sorted halves using auxiliary storage.",
  },
  quick: {
    name: "Quick Sort",
    best: "O(n log n)",
    avg: "O(n log n)",
    worst: "O(n²)",
    stable: false,
    inPlace: true,
    memory: "O(log n)",
    description: "Partitions around a pivot, then recursively sorts sub-arrays.",
  },
  heap: {
    name: "Heap Sort",
    best: "O(n log n)",
    avg: "O(n log n)",
    worst: "O(n log n)",
    stable: false,
    inPlace: true,
    memory: "O(1)",
    description: "Heapifies the array, then repeatedly extracts the maximum.",
  },
  shell: {
    name: "Shell Sort",
    best: "O(n log n)",
    avg: "O(n^4/3)",
    worst: "O(n²)",
    stable: false,
    inPlace: true,
    memory: "O(1)",
    description: "Insertion sort with diminishing gaps — compares distant pairs first.",
  },
  radix: {
    name: "Radix Sort",
    best: "O(nk)",
    avg: "O(nk)",
    worst: "O(nk)",
    stable: true,
    inPlace: false,
    memory: "O(n + k)",
    description: "Sorts by individual digits using counting sort passes (LSD).",
  },
  counting: {
    name: "Counting Sort",
    best: "O(n + k)",
    avg: "O(n + k)",
    worst: "O(n + k)",
    stable: true,
    inPlace: false,
    memory: "O(k)",
    description: "Counts occurrences of each value, then reconstructs the sorted array.",
  },
  cocktail: {
    name: "Cocktail Shaker Sort",
    best: "O(n)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: true,
    inPlace: true,
    memory: "O(1)",
    description: "Bidirectional bubble sort — sweeps forward then backward each pass.",
  },
  comb: {
    name: "Comb Sort",
    best: "O(n log n)",
    avg: "O(n² / 2ᵖ)",
    worst: "O(n²)",
    stable: false,
    inPlace: true,
    memory: "O(1)",
    description: "Bubble sort with a shrinking gap (factor 1.3) that eliminates turtles early.",
  },
  gnome: {
    name: "Gnome Sort",
    best: "O(n)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: true,
    inPlace: true,
    memory: "O(1)",
    description: "Like insertion sort, but swaps backward one step at a time — the garden-gnome algorithm.",
  },
  oddeven: {
    name: "Odd-Even Sort",
    best: "O(n)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: true,
    inPlace: true,
    memory: "O(1)",
    description: "Alternating odd/even adjacent comparison passes; maps cleanly onto parallel hardware.",
  },
  pancake: {
    name: "Pancake Sort",
    best: "O(n)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: false,
    inPlace: true,
    memory: "O(1)",
    description: "Sorts by prefix reversals: flip the max to the front, then into place.",
  },
  cycle: {
    name: "Cycle Sort",
    best: "O(n²)",
    avg: "O(n²)",
    worst: "O(n²)",
    stable: false,
    inPlace: true,
    memory: "O(1)",
    description: "Rotates each cycle into place so each element is written at most once — minimal writes.",
  },
  timsort: {
    name: "Timsort",
    best: "O(n)",
    avg: "O(n log n)",
    worst: "O(n log n)",
    stable: true,
    inPlace: false,
    memory: "O(n)",
    description: "Natural mergesort of runs: reverse descending runs, insertion-sort to minrun, then merge.",
  },
};

const LEARNING_CARDS = {
  bubble: {
    trivia: "Bubble sort is one of the simplest algorithms taught in CS101 — yet it inspired early GPU sorting research.",
    useCase: "Educational demos and tiny embedded lists where code size matters more than speed.",
  },
  selection: {
    trivia: "Selection sort always makes exactly n−1 swaps, no matter the input order.",
    useCase: "Flash memory systems where writes are expensive and minimizing swaps is critical.",
  },
  insertion: {
    trivia: "Insertion sort is the algorithm behind Timsort's galloping merge for nearly-sorted runs.",
    useCase: "Real-time online sorting — e.g. sorting a hand of playing cards as you receive them.",
  },
  merge: {
    trivia: "Merge sort was invented by John von Neumann in 1945 for the EDVAC computer.",
    useCase: "External sorting of massive datasets that don't fit in RAM (database indexes, log files).",
  },
  quick: {
    trivia: "Tony Hoare invented Quick Sort at age 26 while on an exchange program in Moscow.",
    useCase: "General-purpose in-memory sorting — used in C's qsort, Python's Timsort hybrid, and more.",
  },
  heap: {
    trivia: "Heap sort guarantees O(n log n) without extra arrays — unlike merge sort.",
    useCase: "Priority queues and real-time systems needing predictable worst-case performance.",
  },
  shell: {
    trivia: "Donald Shell published Shell Sort in 1959 — it was the first algorithm to beat O(n²) in practice.",
    useCase: "Medium-sized in-memory arrays where simplicity beats merge sort's overhead.",
  },
  radix: {
    trivia: "Radix sort can sort integers faster than comparison-based sorts when the key range is bounded.",
    useCase: "Sorting fixed-width integers — IP addresses, zip codes, and database column indexes.",
  },
  counting: {
    trivia: "Counting sort is not comparison-based — it sidesteps the O(n log n) lower bound entirely.",
    useCase: "Sorting exam scores (0–100), histograms, and vote tallies with a small value range.",
  },
  cocktail: {
    trivia: "Cocktail shaker sort is also called bidirectional bubble sort or shaker sort.",
    useCase: "Teaching bidirectional scanning — slightly better than bubble on reversed arrays.",
  },
  comb: {
    trivia: "Comb sort’s 1.3 shrink factor was chosen empirically — it is still one of the best simple gap sequences.",
    useCase: "A drop-in upgrade over bubble sort when you want fewer passes without extra memory.",
  },
  gnome: {
    trivia: "Hamidoon Sallam described gnome sort as a garden gnome sorting flower pots: step forward, or swap back.",
    useCase: "Tiny in-place sorts and teaching the relationship between insertion sort and adjacent swaps.",
  },
  oddeven: {
    trivia: "Odd-even (Brick) sort is the comparison network cousin of bubble sort, popular on early parallel machines.",
    useCase: "GPU and hardware pipelines where even/odd neighbor compares can run simultaneously.",
  },
  pancake: {
    trivia: "Pancake sorting asks: how many spatula flips to sort a stack? Bill Gates published a bound on it in 1979.",
    useCase: "Rewriting prefixes in genome rearrangement and any “only reverse a prefix” constraint.",
  },
  cycle: {
    trivia: "Cycle sort is theoretically optimal for writes: every item is written at most once, so a reversed unique list needs ≤ n writes.",
    useCase: "EEPROM / flash where writes wear the medium, and any setting where comparisons are cheap but stores are not.",
  },
  timsort: {
    trivia: "Timsort (Tim Peters, 2002) is Python’s default sort and Java’s for objects — it gallops over already-sorted runs.",
    useCase: "Real-world arrays that are often partially sorted: logs, user-generated lists, and stable object sorts.",
  },
};

const DATASET_LABELS = {
  random: "Random",
  sorted: "Sorted",
  "nearly-sorted": "Nearly Sorted",
  reversed: "Reversed",
  "few-unique": "Few Unique",
  sawtooth: "Sawtooth",
  custom: "Custom Input",
};

const HISTORY_KEY = "sortLabHistory";
const QUIZ_SCORE_KEY = "sortLabQuizScore";
const MAX_HISTORY = 8;

// ---------- DOM references ----------
const $ = (id) => document.getElementById(id);

function isTypingTarget(el) {
  if (!el || !el.tagName) return false;
  const tag = el.tagName;
  return tag === "INPUT" || tag === "TEXTAREA" || tag === "SELECT";
}

function isCheatSheetKey(e) {
  return e.key === "?" || (e.shiftKey && (e.key === "/" || e.code === "Slash"));
}

const dom = {
  algorithm: $("algorithm"),
  algorithmRace: $("algorithmRace"),
  dataset: $("dataset"),
  size: $("size"),
  speed: $("speed"),
  sizeValue: $("sizeValue"),
  speedValue: $("speedValue"),
  raceMode: $("raceMode"),
  stepMode: $("stepMode"),
  teachingMode: $("teachingMode"),
  soundToggle: $("soundToggle"),
  themeToggle: $("themeToggle"),
  customArrayField: $("customArrayField"),
  customArray: $("customArray"),
  applyCustomBtn: $("applyCustomBtn"),
  customArrayError: $("customArrayError"),
  generateBtn: $("generateBtn"),
  startBtn: $("startBtn"),
  pauseBtn: $("pauseBtn"),
  stopBtn: $("stopBtn"),
  nextStepBtn: $("nextStepBtn"),
  resetBtn: $("resetBtn"),
  tournamentBtn: $("tournamentBtn"),
  exportCsvBtn: $("exportCsvBtn"),
  copySummaryBtn: $("copySummaryBtn"),
  visualizer: $("visualizer"),
  visualizerRace: $("visualizerRace"),
  panePrimary: $("panePrimary"),
  paneSecondary: $("paneSecondary"),
  metricsPrimary: $("metricsPrimary"),
  metricsSecondary: $("metricsSecondary"),
  profilePanel: $("profilePanel"),
  historyList: $("historyList"),
  legend: $("legend"),
  statusText: $("statusText"),
  toast: $("toast"),
  teachingPanel: $("teachingPanel"),
  teachingText: $("teachingText"),
  opsChart: $("opsChart"),
  tournamentPanel: $("tournamentPanel"),
  leaderboard: $("leaderboard"),
  comparisonPanel: $("comparisonPanel"),
  comparisonMatrix: $("comparisonMatrix"),
  a11yAnnouncer: $("a11yAnnouncer"),
  shareUrlBtn: $("shareUrlBtn"),
  presentationBtn: $("presentationBtn"),
  quizMode: $("quizMode"),
  identityColors: $("identityColors"),
  quizScore: $("quizScore"),
  quizPanel: $("quizPanel"),
  quizGuessGrid: $("quizGuessGrid"),
  quizFeedback: $("quizFeedback"),
  recommenderContent: $("recommenderContent"),
  learningCard: $("learningCard"),
  learningCardsPanel: $("learningCardsPanel"),
  learningTrivia: $("learningTrivia"),
  learningUseCase: $("learningUseCase"),
  cheatSheet: $("cheatSheet"),
  cheatSheetBtn: $("cheatSheetBtn"),
  cheatSheetClose: $("cheatSheetClose"),
  heatmapPrimary: $("heatmapPrimary"),
  heatmapSecondary: $("heatmapSecondary"),
  countingArrayPanel: $("countingArrayPanel"),
  countingArrayDisplay: $("countingArrayDisplay"),
  panePrimaryLabel: $("panePrimaryLabel"),
  presentationOverlay: $("presentationOverlay"),
  presentationAlgo: $("presentationAlgo"),
  presentationMetrics: $("presentationMetrics"),
  presentationExitBtn: $("presentationExitBtn"),
  presentationVisualizer: $("presentationVisualizer"),
  presentationHeatmap: $("presentationHeatmap"),
};

// ---------- Dataset analysis & recommender ----------
function analyzeDataset(arr) {
  const n = arr.length;
  const unique = new Set(arr).size;
  let inversions = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (arr[i] > arr[j]) inversions++;
    }
  }

  const maxInversions = (n * (n - 1)) / 2 || 1;
  const sortedness = 1 - inversions / maxInversions;
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;

  return { n, unique, inversions, sortedness, uniqueRatio: unique / n, min, max, range };
}

function recommendAlgorithm(arr) {
  const stats = analyzeDataset(arr);

  if (stats.sortedness > 0.92) {
    return {
      algorithm: "insertion",
      reason: `Dataset is ${Math.round(stats.sortedness * 100)}% sorted — Insertion Sort runs in near O(n) time on already-ordered data.`,
      stats,
    };
  }

  if (stats.unique <= 12 && stats.range <= 100 && stats.n >= 15) {
    return {
      algorithm: "counting",
      reason: `Only ${stats.unique} distinct values in a range of ${stats.range} — Counting Sort avoids comparisons entirely.`,
      stats,
    };
  }

  if (stats.uniqueRatio < 0.2 && stats.n >= 20) {
    return {
      algorithm: "radix",
      reason: `Low cardinality (${stats.unique} unique / ${stats.n} elements) — Radix Sort distributes by digits efficiently.`,
      stats,
    };
  }

  if (stats.sortedness < 0.15) {
    return {
      algorithm: "merge",
      reason: "Highly disordered (likely reversed) — Merge Sort guarantees O(n log n) regardless of input order.",
      stats,
    };
  }

  if (stats.n <= 25) {
    return {
      algorithm: "insertion",
      reason: `Small array (n=${stats.n}) — Insertion Sort has low overhead and excellent cache locality.`,
      stats,
    };
  }

  return {
    algorithm: "quick",
    reason: "General-purpose random data — Quick Sort offers excellent average-case performance in practice.",
    stats,
  };
}

function heatmapColor(ratio) {
  const low = getComputedStyle(document.documentElement).getPropertyValue("--heatmap-low").trim() || "#dbeafe";
  const high = getComputedStyle(document.documentElement).getPropertyValue("--heatmap-high").trim() || "#dc2626";

  const parse = (hex) => {
    const h = hex.replace("#", "");
    return [
      parseInt(h.slice(0, 2), 16),
      parseInt(h.slice(2, 4), 16),
      parseInt(h.slice(4, 6), 16),
    ];
  };

  const [r1, g1, b1] = parse(low.length === 7 ? low : "#dbeafe");
  const [r2, g2, b2] = parse(high.length === 7 ? high : "#dc2626");
  const t = Math.min(1, Math.max(0, ratio));
  const r = Math.round(r1 + (r2 - r1) * t);
  const g = Math.round(g1 + (g2 - g1) * t);
  const b = Math.round(b1 + (b2 - b1) * t);
  return `rgb(${r}, ${g}, ${b})`;
}

// ---------- Dataset generators ----------
function randomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function valueFromIndex(i, size) {
  return Math.floor(((i + 1) / size) * 90) + 5;
}

function generateDataset(type, size) {
  switch (type) {
    case "sorted":
      return Array.from({ length: size }, (_, i) => valueFromIndex(i, size));

    case "reversed":
      return Array.from({ length: size }, (_, i) => valueFromIndex(size - 1 - i, size));

    case "nearly-sorted": {
      const arr = Array.from({ length: size }, (_, i) => valueFromIndex(i, size));
      const swaps = Math.max(1, Math.floor(size * 0.05));
      for (let s = 0; s < swaps; s++) {
        const a = randomInt(0, size - 1);
        const b = randomInt(0, size - 1);
        [arr[a], arr[b]] = [arr[b], arr[a]];
      }
      return arr;
    }

    case "few-unique": {
      const uniques = [12, 28, 44, 60, 76, 92];
      return Array.from({ length: size }, () => uniques[randomInt(0, uniques.length - 1)]);
    }

    case "sawtooth": {
      const period = Math.max(4, Math.floor(size / 6));
      return Array.from({ length: size }, (_, i) => {
        const phase = i % period;
        const ascending = phase < period / 2;
        const pos = ascending ? phase : period - phase;
        return Math.floor((pos / (period / 2)) * 85) + 10;
      });
    }

    case "random":
    default:
      return Array.from({ length: size }, () => randomInt(5, 95));
  }
}

function parseCustomArray(input, maxSize = 120) {
  const trimmed = input.trim();
  if (!trimmed) {
    return { error: "Enter comma-separated values or a JSON array." };
  }

  let values;
  try {
    if (trimmed.startsWith("[")) {
      values = JSON.parse(trimmed);
      if (!Array.isArray(values)) {
        return { error: "JSON input must be an array." };
      }
    } else {
      values = trimmed.split(/[,\s]+/).filter(Boolean).map(Number);
    }
  } catch {
    return { error: "Invalid JSON array format." };
  }

  if (!values.length) {
    return { error: "Array must contain at least one number." };
  }

  if (values.length > maxSize) {
    return { error: `Maximum ${maxSize} elements allowed.` };
  }

  if (values.some((v) => typeof v !== "number" || !Number.isFinite(v))) {
    return { error: "All values must be valid numbers." };
  }

  const min = Math.min(...values);
  const max = Math.max(...values);
  const range = max - min || 1;
  const normalized = values.map((v) => Math.round(((v - min) / range) * 85 + 10));

  return { data: normalized, original: values };
}

// ---------- Operations sparkline chart ----------
class OperationsChart {
  constructor(canvas) {
    this.canvas = canvas;
    this.ctx = canvas ? canvas.getContext("2d") : null;
    this.points = [];
    if (canvas) {
      this.resize();
      window.addEventListener("resize", () => this.resize());
    }
  }

  resize() {
    if (!this.canvas || !this.ctx) return;
    const wrap = this.canvas.parentElement;
    const w = Math.max(120, wrap.clientWidth - 110);
    const dpr = window.devicePixelRatio || 1;
    this.canvas.width = Math.floor(w * dpr);
    this.canvas.height = Math.floor(56 * dpr);
    this.canvas.style.width = `${w}px`;
    this.canvas.style.height = "56px";
    this.ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
    this.draw();
  }

  reset() {
    this.points = [];
    this.draw();
  }

  push(totalOps) {
    this.points.push(totalOps);
    if (this.points.length > 600) this.points.shift();
    this.draw();
  }

  draw() {
    if (!this.ctx || !this.canvas) return;

    const w = this.canvas.width / (window.devicePixelRatio || 1);
    const h = 56;
    this.ctx.clearRect(0, 0, w, h);

    if (this.points.length < 2) return;

    const max = Math.max(...this.points, 1);
    const pad = 4;
    const innerW = w - pad * 2;
    const innerH = h - pad * 2;
    const color = getComputedStyle(document.documentElement)
      .getPropertyValue("--primary")
      .trim() || "#2563eb";

    this.ctx.strokeStyle = color;
    this.ctx.lineWidth = 2;
    this.ctx.beginPath();

    this.points.forEach((val, i) => {
      const x = pad + (i / (this.points.length - 1)) * innerW;
      const y = pad + innerH - (val / max) * innerH;
      if (i === 0) this.ctx.moveTo(x, y);
      else this.ctx.lineTo(x, y);
    });

    this.ctx.stroke();
    this.ctx.lineTo(pad + innerW, pad + innerH);
    this.ctx.lineTo(pad, pad + innerH);
    this.ctx.closePath();
    this.ctx.fillStyle = color.includes("rgb") ? color.replace(")", ", 0.12)").replace("rgb", "rgba") : "rgba(37, 99, 235, 0.12)";
    this.ctx.fill();
  }
}

// ---------- Audio ----------
class AudioManager {
  constructor() {
    this.enabled = localStorage.getItem("sound") === "true";
    this.ctx = null;
  }

  init() {
    if (!this.ctx) {
      this.ctx = new (window.AudioContext || window.webkitAudioContext)();
    }
    if (this.ctx.state === "suspended") {
      this.ctx.resume();
    }
  }

  beep(frequency = 440, duration = 0.03, volume = 0.04) {
    if (!this.enabled) return;
    this.init();
    const osc = this.ctx.createOscillator();
    const gain = this.ctx.createGain();
    osc.type = "sine";
    osc.frequency.value = frequency;
    gain.gain.value = volume;
    osc.connect(gain);
    gain.connect(this.ctx.destination);
    osc.start();
    osc.stop(this.ctx.currentTime + duration);
  }

  compare() {
    this.beep(520, 0.02, 0.03);
  }

  swap() {
    this.beep(280, 0.04, 0.05);
  }

  write() {
    this.beep(400, 0.025, 0.035);
  }

  setEnabled(enabled) {
    this.enabled = enabled;
    localStorage.setItem("sound", String(enabled));
  }
}

// ---------- Metrics ----------
class Metrics {
  constructor() {
    this.reset();
  }

  reset() {
    this.comparisons = 0;
    this.swaps = 0;
    this.writes = 0;
    this.startTime = 0;
    this.elapsedMs = 0;
  }

  start() {
    this.reset();
    this.startTime = performance.now();
  }

  finish() {
    this.elapsedMs = Math.round(performance.now() - this.startTime);
  }
}

// ---------- Sort runner (one visualization pane) ----------
class SortRunner {
  constructor({ container, metricsEl, heatmapEl, label }) {
    this.container = container;
    this.metricsEl = metricsEl;
    this.heatmapEl = heatmapEl;
    this.label = label;
    this.array = [];
    this.ids = [];
    this.bars = [];
    this.accessCounts = [];
    this.identityColors = false;
    this.metrics = new Metrics();
    this.paused = false;
    this.stopped = false;
    this.stepMode = false;
    this.silent = false;
    this.teachingMode = false;
    this.stepResolver = null;
    this.isRunning = false;
    this.audio = null;
    this.speedSlider = null;
    this.onNarrate = null;
    this.onOperation = null;
    this.onVisualUpdate = null;
    this.onCountingArrayUpdate = null;
    this.currentGap = 0;
    this.currentDigitExp = 1;
  }

  configure({
    audio,
    speedSlider,
    stepMode,
    silent = false,
    teachingMode = false,
    identityColors,
    onNarrate,
    onOperation,
    onVisualUpdate,
    onCountingArrayUpdate,
  }) {
    this.audio = audio;
    this.speedSlider = speedSlider;
    this.stepMode = stepMode;
    this.silent = silent;
    this.teachingMode = teachingMode;
    if (identityColors !== undefined) this.identityColors = identityColors;
    this.onNarrate = onNarrate || null;
    this.onOperation = onOperation || null;
    this.onVisualUpdate = onVisualUpdate || null;
    this.onCountingArrayUpdate = onCountingArrayUpdate || null;
  }

  setArray(data) {
    this.array = [...data];
    this.ids = data.map((_, i) => i);
    this.accessCounts = new Array(data.length).fill(0);
    this.renderBars();
    this.renderHeatmap();
  }

  identityHue(id) {
    return `hsl(${(Number(id) * 47) % 360} 70% 50%)`;
  }

  paintBar(i) {
    if (this.silent) return;
    const bar = this.bars[i];
    if (!bar) return;
    const value = this.array[i];
    bar.style.height = `${value}%`;
    if (this.array.length <= 24) bar.textContent = String(value);
    else bar.textContent = "";
    if (this.identityColors) {
      bar.style.setProperty("--bar-identity", this.identityHue(this.ids[i]));
      bar.classList.add("identity");
    } else {
      bar.style.removeProperty("--bar-identity");
      bar.classList.remove("identity");
    }
  }

  applyBarStyles() {
    if (this.silent) return;
    for (let i = 0; i < this.bars.length; i++) this.paintBar(i);
  }

  renderBars() {
    if (this.silent) return;
    this.container.innerHTML = "";
    this.bars = this.array.map((value) => {
      const bar = document.createElement("div");
      bar.className = "bar";
      bar.style.height = `${value}%`;
      bar.setAttribute("role", "presentation");
      this.container.appendChild(bar);
      return bar;
    });
    this.applyBarStyles();
  }

  clearStateClasses() {
    this.bars.forEach((bar) => {
      bar.classList.remove("compare", "swap", "sorted", "pivot", "write", "digit", "gap", "bucket");
    });
  }

  trackAccess(...indices) {
    indices.forEach((i) => {
      if (i >= 0 && i < this.accessCounts.length) {
        this.accessCounts[i]++;
      }
    });
  }

  renderHeatmap() {
    if (!this.heatmapEl || this.silent) return;

    const n = this.array.length;
    if (this.heatmapEl.children.length !== n) {
      this.heatmapEl.innerHTML = "";
      for (let i = 0; i < n; i++) {
        const cell = document.createElement("div");
        cell.className = "heatmap-cell";
        cell.title = `Index ${i}: 0 accesses`;
        this.heatmapEl.appendChild(cell);
      }
    }

    const max = Math.max(...this.accessCounts, 1);
    Array.from(this.heatmapEl.children).forEach((cell, i) => {
      const count = this.accessCounts[i] || 0;
      cell.style.background = heatmapColor(count / max);
      cell.title = `Index ${i}: ${count} access${count === 1 ? "" : "es"}`;
    });
  }

  notifyVisualUpdate() {
    this.renderHeatmap();
    this.onVisualUpdate?.(this);
  }

  narrate(message) {
    if (!this.teachingMode || this.silent || !this.onNarrate) return;
    this.onNarrate(message);
  }

  recordOperation() {
    if (this.silent || !this.onOperation) return;
    const total = this.metrics.comparisons + this.metrics.swaps + this.metrics.writes;
    this.onOperation(total);
  }

  updateMetricsDisplay() {
    if (!this.metricsEl) return;
    const m = this.metrics;
    this.metricsEl.innerHTML = `
      <span class="metric"><strong>${m.comparisons}</strong> comparisons</span>
      <span class="metric"><strong>${m.swaps}</strong> swaps</span>
      <span class="metric"><strong>${m.writes}</strong> writes</span>
      <span class="metric"><strong>${m.elapsedMs}</strong> ms</span>
    `;
  }

  tickElapsed() {
    if (this.metrics.startTime) {
      this.metrics.elapsedMs = Math.round(performance.now() - this.metrics.startTime);
      this.updateMetricsDisplay();
    }
  }

  async waitStep() {
    if (this.stopped) throw new Error("STOPPED");

    if (this.silent) {
      return;
    }

    if (this.stepMode) {
      await new Promise((resolve) => {
        this.stepResolver = resolve;
      });
      if (this.stopped) throw new Error("STOPPED");
      return;
    }

    while (this.paused) {
      await new Promise((r) => setTimeout(r, 50));
      if (this.stopped) throw new Error("STOPPED");
    }

    let delay = 202 - this.speedSlider.value * 2;
    if (
      typeof window !== "undefined" &&
      window.matchMedia &&
      window.matchMedia("(prefers-reduced-motion: reduce)").matches
    ) {
      delay = 0;
    }
    await new Promise((r) => setTimeout(r, delay));
    this.tickElapsed();
  }

  resolveStep() {
    if (this.stepResolver) {
      const resolve = this.stepResolver;
      this.stepResolver = null;
      resolve();
    }
  }

  async compare(i, j) {
    this.metrics.comparisons++;
    this.trackAccess(i, j);
    if (!this.silent) {
      this.bars[i]?.classList.add("compare");
      this.bars[j]?.classList.add("compare");
    }
    this.audio?.compare();
    this.updateMetricsDisplay();
    this.narrate(`Now comparing indices ${i} and ${j} (values ${this.array[i]} and ${this.array[j]}).`);
    this.recordOperation();
    this.notifyVisualUpdate();
    await this.waitStep();
  }

  /**
   * Compare auxiliary merge keys — not the live bars at i/j, which may already
   * have been overwritten earlier in this merge.
   */
  async compareAux(leftIdx, rightIdx, leftVal, rightVal) {
    this.metrics.comparisons++;
    this.trackAccess(leftIdx, rightIdx);
    this.audio?.compare();
    this.updateMetricsDisplay();
    this.narrate(`Comparing merge keys ${leftVal} (left ${leftIdx}) vs ${rightVal} (right ${rightIdx})`);
    this.recordOperation();
    this.notifyVisualUpdate();
    await this.waitStep();
  }

  clearCompare(i, j) {
    this.bars[i]?.classList.remove("compare");
    this.bars[j]?.classList.remove("compare");
  }

  async swap(i, j) {
    this.metrics.swaps++;
    this.metrics.writes += 2;
    this.trackAccess(i, j);
    [this.array[i], this.array[j]] = [this.array[j], this.array[i]];
    [this.ids[i], this.ids[j]] = [this.ids[j], this.ids[i]];
    if (!this.silent) {
      this.paintBar(i);
      this.paintBar(j);
      this.bars[i].classList.add("swap");
      this.bars[j].classList.add("swap");
    }
    this.audio?.swap();
    this.updateMetricsDisplay();
    this.narrate(`Swapping indices ${i} and ${j}.`);
    this.recordOperation();
    this.notifyVisualUpdate();
    await this.waitStep();
    this.bars[i]?.classList.remove("swap");
    this.bars[j]?.classList.remove("swap");
  }

  async write(i, value, id) {
    this.metrics.writes++;
    this.trackAccess(i);
    this.array[i] = value;
    if (id !== undefined && id !== null) this.ids[i] = id;
    if (!this.silent) {
      this.paintBar(i);
      this.bars[i].classList.add("write");
    }
    this.audio?.write();
    this.updateMetricsDisplay();
    this.narrate(`Writing value ${value} to index ${i}.`);
    this.recordOperation();
    this.notifyVisualUpdate();
    await this.waitStep();
    this.bars[i]?.classList.remove("write");
  }

  markSorted(i) {
    this.bars[i]?.classList.add("sorted");
  }

  async markPivot(i) {
    this.trackAccess(i);
    this.bars[i]?.classList.add("pivot");
    this.narrate(`Pivot selected at index ${i} (value ${this.array[i]}).`);
    this.notifyVisualUpdate();
    await this.waitStep();
  }

  clearPivot(i) {
    this.bars[i]?.classList.remove("pivot");
  }

  async run(algorithm) {
    this.isRunning = true;
    this.stopped = false;
    this.paused = false;
    this.metrics.start();
    this.clearStateClasses();

    const runners = {
      bubble: () => this.bubbleSort(),
      selection: () => this.selectionSort(),
      insertion: () => this.insertionSort(),
      merge: () => this.mergeSort(),
      quick: () => this.quickSort(),
      heap: () => this.heapSort(),
      shell: () => this.shellSort(),
      radix: () => this.radixSort(),
      counting: () => this.countingSort(),
      cocktail: () => this.cocktailShakerSort(),
      comb: () => this.combSort(),
      gnome: () => this.gnomeSort(),
      oddeven: () => this.oddEvenSort(),
      pancake: () => this.pancakeSort(),
      cycle: () => this.cycleSort(),
      timsort: () => this.timsort(),
    };

    try {
      await runners[algorithm]();
      if (!this.silent) {
        this.bars.forEach((bar) => bar.classList.add("sorted"));
      }
      this.narrate("Sorting complete — all elements are in order.");
    } catch (err) {
      if (err.message !== "STOPPED") throw err;
    } finally {
      this.metrics.finish();
      this.updateMetricsDisplay();
      this.isRunning = false;
    }
  }

  async bubbleSort() {
    const n = this.array.length;
    for (let i = 0; i < n - 1; i++) {
      let swapped = false;
      for (let j = 0; j < n - i - 1; j++) {
        await this.compare(j, j + 1);
        if (this.array[j] > this.array[j + 1]) {
          await this.swap(j, j + 1);
          swapped = true;
        }
        this.clearCompare(j, j + 1);
      }
      this.markSorted(n - i - 1);
      if (!swapped) {
        for (let k = 0; k < n - i - 1; k++) this.markSorted(k);
        break;
      }
    }
    this.markSorted(0);
  }

  async selectionSort() {
    const n = this.array.length;
    for (let i = 0; i < n - 1; i++) {
      let minIdx = i;
      if (!this.silent) this.bars[minIdx].classList.add("compare");

      for (let j = i + 1; j < n; j++) {
        await this.compare(j, minIdx);
        if (this.array[j] < this.array[minIdx]) {
          this.bars[minIdx]?.classList.remove("compare");
          minIdx = j;
          if (!this.silent) this.bars[minIdx].classList.add("compare");
        } else {
          this.bars[j]?.classList.remove("compare");
        }
      }

      if (minIdx !== i) await this.swap(i, minIdx);
      this.bars[minIdx]?.classList.remove("compare");
      this.markSorted(i);
    }
    this.markSorted(n - 1);
  }

  async insertionSort() {
    const n = this.array.length;
    this.markSorted(0);

    for (let i = 1; i < n; i++) {
      let j = i;
      if (!this.silent) this.bars[i].classList.add("compare");

      while (j > 0) {
        await this.compare(j - 1, j);
        if (this.array[j - 1] > this.array[j]) {
          await this.swap(j - 1, j);
          j--;
        } else {
          this.clearCompare(j - 1, j);
          break;
        }
        this.clearCompare(j - 1, j);
      }

      this.bars[i]?.classList.remove("compare");
      for (let k = 0; k <= i; k++) this.markSorted(k);
    }
  }

  async mergeSort() {
    const aux = [...this.array];
    const auxIds = [...this.ids];
    await this.mergeSortRange(0, this.array.length - 1, aux, auxIds);
  }

  async mergeSortRange(low, high, aux, auxIds) {
    if (low >= high) return;
    const mid = Math.floor((low + high) / 2);
    this.narrate(`Merge sort: dividing range [${low}…${high}] at midpoint ${mid}.`);
    await this.mergeSortRange(low, mid, aux, auxIds);
    await this.mergeSortRange(mid + 1, high, aux, auxIds);
    await this.merge(low, mid, high, aux, auxIds);
  }

  async merge(low, mid, high, aux, auxIds) {
    this.narrate(`Merging sorted halves [${low}…${mid}] and [${mid + 1}…${high}].`);
    for (let k = low; k <= high; k++) {
      aux[k] = this.array[k];
      auxIds[k] = this.ids[k];
    }

    let i = low;
    let j = mid + 1;
    let k = low;

    while (i <= mid && j <= high) {
      const leftVal = aux[i];
      const rightVal = aux[j];
      await this.compareAux(i, j, leftVal, rightVal);
      if (leftVal <= rightVal) {
        await this.write(k, leftVal, auxIds[i]);
        i++;
      } else {
        await this.write(k, rightVal, auxIds[j]);
        j++;
      }
      k++;
    }

    while (i <= mid) {
      await this.write(k, aux[i], auxIds[i]);
      i++;
      k++;
    }

    while (j <= high) {
      await this.write(k, aux[j], auxIds[j]);
      j++;
      k++;
    }
  }

  async quickSort(low = 0, high = this.array.length - 1) {
    if (low < high) {
      const pivotIdx = await this.partition(low, high);
      await this.quickSort(low, pivotIdx - 1);
      await this.quickSort(pivotIdx + 1, high);
    }
  }

  async partition(low, high) {
    await this.markPivot(high);
    const pivotValue = this.array[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      await this.compare(j, high);
      if (this.array[j] < pivotValue) {
        i++;
        if (i !== j) await this.swap(i, j);
      }
      this.clearCompare(j, high);
    }

    await this.swap(i + 1, high);
    this.clearPivot(high);
    this.markSorted(i + 1);
    return i + 1;
  }

  async heapSort() {
    const n = this.array.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      await this.heapify(n, i);
    }

    for (let i = n - 1; i > 0; i--) {
      await this.swap(0, i);
      this.markSorted(i);
      await this.heapify(i, 0);
    }
    this.markSorted(0);
  }

  async heapify(size, root) {
    let largest = root;
    const left = 2 * root + 1;
    const right = 2 * root + 2;

    if (left < size) {
      await this.compare(left, largest);
      if (this.array[left] > this.array[largest]) largest = left;
      this.clearCompare(left, root);
    }

    if (right < size) {
      const compareWith = largest;
      await this.compare(right, compareWith);
      if (this.array[right] > this.array[compareWith]) largest = right;
      this.clearCompare(right, compareWith);
    }

    if (largest !== root) {
      await this.swap(root, largest);
      await this.heapify(size, largest);
    }
  }

  async shellSort() {
    const n = this.array.length;
    let gap = Math.floor(n / 2);

    while (gap > 0) {
      this.currentGap = gap;
      this.narrate(`Shell sort: starting pass with gap = ${gap}.`);

      for (let i = gap; i < n; i++) {
        const temp = this.array[i];
        const tempId = this.ids[i];
        let j = i;
        if (!this.silent) this.bars[i]?.classList.add("gap");

        while (j >= gap) {
          await this.compare(j - gap, j);
          if (!this.silent) this.bars[j - gap]?.classList.add("gap");
          this.narrate(
            `Comparing indices ${j - gap} and ${j} (${gap} apart): ${this.array[j - gap]} vs ${temp}.`
          );

          if (this.array[j - gap] > temp) {
            await this.write(j, this.array[j - gap], this.ids[j - gap]);
            j -= gap;
          } else {
            this.clearCompare(j - gap, j);
            this.bars[j - gap]?.classList.remove("gap");
            break;
          }
          this.clearCompare(j - gap, j);
          this.bars[j - gap]?.classList.remove("gap");
        }

        if (j !== i) {
          await this.write(j, temp, tempId);
        }
        this.bars[i]?.classList.remove("gap");
      }

      gap = Math.floor(gap / 2);
    }
  }

  async radixSort() {
    const max = Math.max(...this.array);
    const placeNames = ["ones", "tens", "hundreds"];
    let exp = 1;
    let pass = 0;

    while (Math.floor(max / exp) > 0) {
      this.currentDigitExp = exp;
      const place = placeNames[pass] || `10^${pass}`;
      this.narrate(`Radix sort pass ${pass + 1}: sorting by ${place} digit.`);
      await this.radixCountingSort(exp);
      exp *= 10;
      pass++;
    }
  }

  async radixCountingSort(exp) {
    const n = this.array.length;
    const output = new Array(n);
    const count = new Array(10).fill(0);

    for (let i = 0; i < n; i++) {
      const digit = Math.floor(this.array[i] / exp) % 10;
      if (!this.silent) this.bars[i]?.classList.add("digit");
      this.narrate(`Counting digit ${digit} at index ${i} (value ${this.array[i]}).`);
      count[digit]++;
      await this.waitStep();
      this.bars[i]?.classList.remove("digit");
    }

    for (let i = 1; i < 10; i++) {
      count[i] += count[i - 1];
    }

    const outputIds = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
      const digit = Math.floor(this.array[i] / exp) % 10;
      const pos = count[digit] - 1;
      output[pos] = this.array[i];
      outputIds[pos] = this.ids[i];
      this.narrate(`Placing ${this.array[i]} into bucket position ${pos} (digit ${digit}).`);
      count[digit]--;
      if (!this.silent) {
        this.bars[i]?.classList.add("digit");
        await this.waitStep();
        this.bars[i]?.classList.remove("digit");
      }
    }

    for (let i = 0; i < n; i++) {
      await this.write(i, output[i], outputIds[i]);
      if (!this.silent) {
        this.bars[i]?.classList.add("digit");
        await this.waitStep();
        this.bars[i]?.classList.remove("digit");
      }
    }
  }

  async countingSort() {
    const n = this.array.length;
    const min = Math.min(...this.array);
    const max = Math.max(...this.array);
    const range = max - min + 1;
    const count = new Array(range).fill(0);

    this.narrate(`Counting sort: value range ${min}…${max} (${range} buckets).`);

    for (let i = 0; i < n; i++) {
      const bucket = this.array[i] - min;
      this.trackAccess(i);
      if (!this.silent) this.bars[i]?.classList.add("bucket");
      count[bucket]++;
      this.metrics.writes++;
      this.onCountingArrayUpdate?.(count, min, max, bucket);
      this.narrate(`Incrementing count for value ${this.array[i]} (bucket ${bucket}).`);
      this.recordOperation();
      this.notifyVisualUpdate();
      await this.waitStep();
      this.bars[i]?.classList.remove("bucket");
    }

    for (let i = 1; i < range; i++) {
      count[i] += count[i - 1];
      this.onCountingArrayUpdate?.(count, min, max, i);
      this.narrate(`Prefix sum at bucket ${i}: cumulative count = ${count[i]}.`);
      this.recordOperation();
      await this.waitStep();
    }

    const output = new Array(n);
    const outputIds = new Array(n);
    for (let i = n - 1; i >= 0; i--) {
      const bucket = this.array[i] - min;
      this.trackAccess(i);
      const pos = count[bucket] - 1;
      output[pos] = this.array[i];
      outputIds[pos] = this.ids[i];
      count[bucket]--;
      if (!this.silent) this.bars[i]?.classList.add("bucket");
      this.onCountingArrayUpdate?.(count, min, max, bucket);
      this.narrate(`Placing ${this.array[i]} at output position ${pos}.`);
      this.recordOperation();
      this.notifyVisualUpdate();
      await this.waitStep();
      this.bars[i]?.classList.remove("bucket");
    }

    for (let i = 0; i < n; i++) {
      await this.write(i, output[i], outputIds[i]);
      if (!this.silent) {
        this.bars[i]?.classList.add("bucket");
        await this.waitStep();
        this.bars[i]?.classList.remove("bucket");
      }
    }
  }

  async cocktailShakerSort() {
    const n = this.array.length;
    let start = 0;
    let end = n - 1;

    while (start < end) {
      let swapped = false;
      this.narrate(`Cocktail pass: scanning forward from ${start} to ${end}.`);

      for (let i = start; i < end; i++) {
        await this.compare(i, i + 1);
        if (this.array[i] > this.array[i + 1]) {
          await this.swap(i, i + 1);
          swapped = true;
        }
        this.clearCompare(i, i + 1);
      }
      this.markSorted(end);
      end--;

      if (!swapped || start >= end) break;

      swapped = false;
      this.narrate(`Cocktail pass: scanning backward from ${end} to ${start}.`);

      for (let i = end; i > start; i--) {
        await this.compare(i - 1, i);
        if (this.array[i - 1] > this.array[i]) {
          await this.swap(i - 1, i);
          swapped = true;
        }
        this.clearCompare(i - 1, i);
      }
      this.markSorted(start);
      start++;
      if (!swapped) break;
    }

    if (n > 0) this.markSorted(start);
  }

  async combSort() {
    const n = this.array.length;
    const shrink = 1.3;
    let gap = n;
    let sorted = false;

    while (!sorted) {
      gap = Math.floor(gap / shrink);
      if (gap <= 1) {
        gap = 1;
        sorted = true;
      }
      this.narrate(`Comb sort: comparing pairs ${gap} apart.`);

      for (let i = 0; i + gap < n; i++) {
        await this.compare(i, i + gap);
        if (this.array[i] > this.array[i + gap]) {
          await this.swap(i, i + gap);
          sorted = false;
        }
        this.clearCompare(i, i + gap);
      }
    }
  }

  async gnomeSort() {
    const n = this.array.length;
    let i = 0;
    this.narrate("Gnome sort: walk forward; swap back when a pair is out of order.");

    while (i < n) {
      if (i === 0) {
        i++;
        continue;
      }
      await this.compare(i - 1, i);
      if (this.array[i] >= this.array[i - 1]) {
        this.clearCompare(i - 1, i);
        i++;
      } else {
        await this.swap(i - 1, i);
        this.clearCompare(i - 1, i);
        i--;
      }
    }
  }

  async oddEvenSort() {
    const n = this.array.length;
    let sorted = false;

    while (!sorted) {
      sorted = true;
      this.narrate("Odd-even sort: odd pass (indices 1, 3, 5…).");
      for (let i = 1; i < n - 1; i += 2) {
        await this.compare(i, i + 1);
        if (this.array[i] > this.array[i + 1]) {
          await this.swap(i, i + 1);
          sorted = false;
        }
        this.clearCompare(i, i + 1);
      }

      this.narrate("Odd-even sort: even pass (indices 0, 2, 4…).");
      for (let i = 0; i < n - 1; i += 2) {
        await this.compare(i, i + 1);
        if (this.array[i] > this.array[i + 1]) {
          await this.swap(i, i + 1);
          sorted = false;
        }
        this.clearCompare(i, i + 1);
      }
    }
  }

  async pancakeSort() {
    const n = this.array.length;

    const flip = async (k) => {
      this.narrate(`Pancake flip: reversing the prefix [0…${k}].`);
      let i = 0;
      let j = k;
      while (i < j) {
        await this.swap(i, j);
        i++;
        j--;
      }
    };

    for (let curr = n; curr > 1; curr--) {
      let maxIdx = 0;
      this.narrate(`Pancake sort: finding the max in the unsorted prefix [0…${curr - 1}].`);
      for (let i = 1; i < curr; i++) {
        const prev = maxIdx;
        await this.compare(i, prev);
        if (this.array[i] > this.array[prev]) maxIdx = i;
        this.clearCompare(i, prev);
      }

      if (maxIdx === curr - 1) {
        this.markSorted(curr - 1);
        continue;
      }
      if (maxIdx !== 0) await flip(maxIdx);
      await flip(curr - 1);
      this.markSorted(curr - 1);
    }
    if (n > 0) this.markSorted(0);
  }

  async cycleSort() {
    const n = this.array.length;
    this.narrate("Cycle sort: rotate each cycle so every value is written into its final index.");

    for (let cycleStart = 0; cycleStart < n - 1; cycleStart++) {
      let item = this.array[cycleStart];
      let itemId = this.ids[cycleStart];
      let pos = cycleStart;

      this.narrate(`Starting a cycle at index ${cycleStart} (item ${item}).`);
      for (let i = cycleStart + 1; i < n; i++) {
        await this.compare(cycleStart, i);
        if (this.array[i] < item) pos++;
        this.clearCompare(cycleStart, i);
      }

      if (pos === cycleStart) {
        this.markSorted(cycleStart);
        continue;
      }

      while (pos < n && item === this.array[pos]) pos++;
      if (pos >= n) continue;
      {
        const displaced = this.array[pos];
        const displacedId = this.ids[pos];
        await this.write(pos, item, itemId);
        item = displaced;
        itemId = displacedId;
      }

      while (pos !== cycleStart) {
        pos = cycleStart;
        for (let i = cycleStart + 1; i < n; i++) {
          await this.compare(cycleStart, i);
          if (this.array[i] < item) pos++;
          this.clearCompare(cycleStart, i);
        }
        while (pos < n && item === this.array[pos]) pos++;
        if (pos >= n) break;
        const displaced = this.array[pos];
        const displacedId = this.ids[pos];
        await this.write(pos, item, itemId);
        item = displaced;
        itemId = displacedId;
      }
      this.markSorted(cycleStart);
    }
    if (n > 0) this.markSorted(n - 1);
  }

  computeMinrun(n) {
    if (n < 2) return n;
    if (n < 64) return Math.min(16, n);
    let r = 0;
    while (n >= 64) {
      r |= n & 1;
      n >>= 1;
    }
    return n + r;
  }

  async reverseRange(lo, hi) {
    this.narrate(`Reversing descending run [${lo}…${hi}] so it ascends.`);
    while (lo < hi) {
      await this.swap(lo, hi);
      lo++;
      hi--;
    }
  }

  async insertionSortRange(lo, hi) {
    this.narrate(`Insertion-sorting run [${lo}…${hi}] up to minrun.`);
    for (let i = lo + 1; i <= hi; i++) {
      let j = i;
      while (j > lo) {
        await this.compare(j - 1, j);
        if (this.array[j - 1] > this.array[j]) {
          await this.swap(j - 1, j);
          j--;
        } else {
          this.clearCompare(j - 1, j);
          break;
        }
        this.clearCompare(j - 1, j);
      }
    }
  }

  async countRunAndMakeAscending(lo, n) {
    if (lo + 1 >= n) return 1;
    await this.compare(lo, lo + 1);
    const descending = this.array[lo] > this.array[lo + 1];
    this.clearCompare(lo, lo + 1);
    let hi = lo + 1;
    if (descending) {
      while (hi + 1 < n) {
        await this.compare(hi, hi + 1);
        const cont = this.array[hi] > this.array[hi + 1];
        this.clearCompare(hi, hi + 1);
        if (!cont) break;
        hi++;
      }
      await this.reverseRange(lo, hi);
    } else {
      while (hi + 1 < n) {
        await this.compare(hi, hi + 1);
        const cont = this.array[hi] < this.array[hi + 1];
        this.clearCompare(hi, hi + 1);
        if (!cont) break;
        hi++;
      }
    }
    return hi - lo + 1;
  }

  async timsort() {
    const n = this.array.length;
    if (n < 2) return;
    const minrun = this.computeMinrun(n);
    this.narrate(`Timsort: scanning natural runs (minrun = ${minrun}).`);

    const runs = [];
    let i = 0;
    while (i < n) {
      let runLen = await this.countRunAndMakeAscending(i, n);
      if (runLen < minrun) {
        const extendTo = Math.min(i + minrun, n) - 1;
        await this.insertionSortRange(i, extendTo);
        runLen = extendTo - i + 1;
      }
      runs.push({ lo: i, hi: i + runLen - 1 });
      this.narrate(`Run [${i}…${i + runLen - 1}] is ready.`);
      i += runLen;
    }

    const aux = [...this.array];
    const auxIds = [...this.ids];
    while (runs.length > 1) {
      const next = [];
      for (let r = 0; r < runs.length; r += 2) {
        if (r + 1 < runs.length) {
          const a = runs[r];
          const b = runs[r + 1];
          this.narrate(`Merging runs [${a.lo}…${a.hi}] and [${b.lo}…${b.hi}].`);
          await this.merge(a.lo, a.hi, b.hi, aux, auxIds);
          next.push({ lo: a.lo, hi: b.hi });
        } else {
          next.push(runs[r]);
        }
      }
      runs.length = 0;
      for (let r = 0; r < next.length; r++) runs.push(next[r]);
    }
  }
}

// ---------- Application ----------
class SortLabApp {
  constructor() {
    this.audio = new AudioManager();
    this.opsChart = new OperationsChart(dom.opsChart);
    this.primary = new SortRunner({
      container: dom.visualizer,
      metricsEl: dom.metricsPrimary,
      heatmapEl: dom.heatmapPrimary,
      label: "Primary",
    });
    this.secondary = new SortRunner({
      container: dom.visualizerRace,
      metricsEl: dom.metricsSecondary,
      heatmapEl: dom.heatmapSecondary,
      label: "Race",
    });
    this.baseArray = [];
    this.isRunning = false;
    this.presentationActive = false;
    this.presentationBars = [];
    this.presentationHeatmapCells = [];
    this.quizAnswer = null;
    this.quizScore = this.loadQuizScore();
    this.lastRunSummary = null;
    this.lastTournamentResults = null;
    this.history = this.loadHistory();
  }

  init() {
    this.initTheme();
    this.initSoundToggle();
    this.loadFromUrl();
    this.bindEvents();
    this.updateProfile();
    this.updateLearningCard();
    this.updateQuizScoreDisplay();
    this.updateTeachingPanel();
    this.updateCustomFieldVisibility();
    this.renderHistory();
    if (dom.dataset.value !== "custom") {
      this.generateArray();
    } else {
      this.applyCustomArray();
    }
    this.updateRecommender();
    this.updateRaceVisibility();
    this.registerServiceWorker();
    this.setStatus("Ready — press S to start or G to generate");
  }

  initTheme() {
    const saved = localStorage.getItem("theme") || "dark";
    document.documentElement.setAttribute("data-theme", saved);
    dom.themeToggle.textContent = saved === "dark" ? "☀️" : "🌙";
    dom.themeToggle.setAttribute("aria-pressed", saved === "dark");
  }

  initSoundToggle() {
    dom.soundToggle.checked = this.audio.enabled;
    dom.soundToggle.setAttribute("aria-pressed", String(this.audio.enabled));
  }

  registerServiceWorker() {
    if ("serviceWorker" in navigator) {
      navigator.serviceWorker.register("./sw.js").catch(() => {});
    }
  }

  bindEvents() {
    dom.size.addEventListener("input", () => {
      dom.sizeValue.textContent = dom.size.value;
      if (!this.isRunning && dom.dataset.value !== "custom") this.generateArray();
    });

    dom.speed.addEventListener("input", () => {
      dom.speedValue.textContent = dom.speed.value;
    });

    dom.algorithm.addEventListener("change", () => {
      this.updateProfile();
      this.updateLearningCard();
    });
    dom.raceMode.addEventListener("change", () => {
      this.updateRaceVisibility();
      dom.algorithmRace.disabled = !dom.raceMode.checked;
    });

    dom.dataset.addEventListener("change", () => {
      this.updateCustomFieldVisibility();
      if (!this.isRunning && dom.dataset.value !== "custom") this.generateArray();
    });

    dom.stepMode.addEventListener("change", () => {
      dom.nextStepBtn.disabled = !dom.stepMode.checked || !this.isRunning;
    });

    dom.teachingMode.addEventListener("change", () => this.updateTeachingPanel());

    if (dom.identityColors) {
      dom.identityColors.addEventListener("change", () => this.syncIdentityColors());
    }

    dom.quizMode.addEventListener("change", () => {
      this.updateProfile();
      if (!dom.quizMode.checked) {
        dom.quizPanel.hidden = true;
        dom.quizFeedback.textContent = "";
      }
    });

    dom.learningCard.addEventListener("click", () => this.flipLearningCard());
    dom.learningCard.addEventListener("keydown", (e) => {
      if (e.code === "Enter" || e.code === "Space") {
        e.preventDefault();
        this.flipLearningCard();
      }
    });

    dom.shareUrlBtn.addEventListener("click", () => this.copyShareUrl());
    dom.presentationBtn.addEventListener("click", () => this.enterPresentation());
    dom.presentationExitBtn.addEventListener("click", () => this.exitPresentation());

    dom.applyCustomBtn.addEventListener("click", () => this.applyCustomArray());

    dom.soundToggle.addEventListener("change", () => {
      this.audio.setEnabled(dom.soundToggle.checked);
      dom.soundToggle.setAttribute("aria-pressed", String(dom.soundToggle.checked));
      if (dom.soundToggle.checked) this.audio.beep(660, 0.05, 0.06);
    });

    dom.generateBtn.addEventListener("click", () => this.generateArray());
    dom.resetBtn.addEventListener("click", () => this.generateArray());
    dom.startBtn.addEventListener("click", () => this.startSort());
    dom.pauseBtn.addEventListener("click", () => this.togglePause());
    dom.stopBtn.addEventListener("click", () => this.stopSort());
    dom.nextStepBtn.addEventListener("click", () => this.nextStep());
    dom.tournamentBtn.addEventListener("click", () => this.runTournament());
    dom.exportCsvBtn.addEventListener("click", () => this.exportCsv());
    dom.copySummaryBtn.addEventListener("click", () => this.copySummary());
    dom.themeToggle.addEventListener("click", () => this.toggleTheme());

    document.addEventListener("keydown", (e) => this.handleKeyboard(e));

    if (dom.cheatSheetBtn) {
      dom.cheatSheetBtn.addEventListener("click", () => this.toggleCheatSheet());
    }
    if (dom.cheatSheetClose) {
      dom.cheatSheetClose.addEventListener("click", () => {
        if (dom.cheatSheet && typeof dom.cheatSheet.close === "function") dom.cheatSheet.close();
      });
    }
    if (dom.cheatSheet) {
      dom.cheatSheet.addEventListener("click", (e) => {
        if (e.target === dom.cheatSheet && typeof dom.cheatSheet.close === "function") dom.cheatSheet.close();
      });
    }
  }

  toggleCheatSheet() {
    const dlg = dom.cheatSheet || document.getElementById("cheatSheet");
    if (!dlg) return;
    if (typeof dlg.showModal === "function") {
      if (dlg.open) dlg.close();
      else dlg.showModal();
    } else {
      dlg.hidden = !dlg.hidden;
    }
  }

  handleKeyboard(e) {
    if (e.code === "Escape" && this.presentationActive) {
      e.preventDefault();
      this.exitPresentation();
      return;
    }

    if (isTypingTarget(e.target)) return;
    if (isCheatSheetKey(e)) {
      e.preventDefault();
      this.toggleCheatSheet();
      return;
    }
    if (dom.cheatSheet && dom.cheatSheet.open) return;

    switch (e.code) {
      case "Space":
        e.preventDefault();
        this.togglePause();
        break;
      case "KeyR":
        this.generateArray();
        break;
      case "KeyG":
        this.generateArray();
        break;
      case "KeyS":
        this.startSort();
        break;
      default:
        break;
    }
  }

  getSize() {
    return parseInt(dom.size.value, 10);
  }

  updateCustomFieldVisibility() {
    const isCustom = dom.dataset.value === "custom";
    dom.customArrayField.hidden = !isCustom;
    if (isCustom) dom.size.disabled = true;
    else dom.size.disabled = this.isRunning;
  }

  showCustomError(message) {
    dom.customArrayError.textContent = message;
    dom.customArrayError.hidden = !message;
  }

  applyCustomArray() {
    if (this.isRunning) return;
    const result = parseCustomArray(dom.customArray.value);
    if (result.error) {
      this.showCustomError(result.error);
      return;
    }

    this.showCustomError("");
    this.baseArray = result.data;
    dom.size.value = result.data.length;
    dom.sizeValue.textContent = result.data.length;
    this.primary.identityColors = this.identityColorsEnabled();
    this.secondary.identityColors = this.identityColorsEnabled();
    this.primary.setArray(this.baseArray);
    this.secondary.setArray(this.baseArray);
    this.primary.metrics.reset();
    this.secondary.metrics.reset();
    this.primary.updateMetricsDisplay();
    this.secondary.updateMetricsDisplay();
    this.updateRecommender();
    this.hideCountingArrayPanel();
    this.setStatus(`Loaded custom array (${result.data.length} elements)`);
    this.announce(`Custom array loaded with ${result.data.length} elements.`);
  }

  generateArray() {
    if (this.isRunning) return;

    if (dom.dataset.value === "custom") {
      this.applyCustomArray();
      return;
    }

    const type = dom.dataset.value;
    const size = this.getSize();
    this.baseArray = generateDataset(type, size);
    this.primary.identityColors = this.identityColorsEnabled();
    this.secondary.identityColors = this.identityColorsEnabled();
    this.primary.setArray(this.baseArray);
    this.secondary.setArray(this.baseArray);
    this.primary.metrics.reset();
    this.secondary.metrics.reset();
    this.primary.updateMetricsDisplay();
    this.secondary.updateMetricsDisplay();
    this.opsChart.reset();
    this.updateRecommender();
    this.hideCountingArrayPanel();
    dom.quizPanel.hidden = true;
    this.setStatus(`Generated ${DATASET_LABELS[type]} dataset (${size} elements)`);
  }

  updateRaceVisibility() {
    const racing = dom.raceMode.checked;
    dom.paneSecondary.classList.toggle("hidden", !racing);
    dom.legend.classList.toggle("race-layout", racing);
    document.body.classList.toggle("race-active", racing);
  }

  updateTeachingPanel() {
    const enabled = dom.teachingMode.checked;
    dom.teachingPanel.classList.toggle("hidden", !enabled);
    if (!enabled) {
      dom.teachingText.textContent = "Enable Teaching Mode to see step-by-step explanations.";
    }
  }

  updateProfile() {
    const profile = ALGORITHM_PROFILES[dom.algorithm.value];
    const quizActive = dom.quizMode.checked;
    const hiddenName = quizActive ? "???" : profile.name;
    dom.profilePanel.classList.toggle("quiz-hidden", quizActive);
    const gridHtml = quizActive
      ? ""
      : `<dl class="profile-grid">
        <div><dt>Best</dt><dd>${profile.best}</dd></div>
        <div><dt>Average</dt><dd>${profile.avg}</dd></div>
        <div><dt>Worst</dt><dd>${profile.worst}</dd></div>
        <div><dt>Stable</dt><dd>${profile.stable ? "Yes" : "No"}</dd></div>
        <div><dt>In-place</dt><dd>${profile.inPlace ? "Yes" : "No"}</dd></div>
        <div><dt>Memory</dt><dd>${profile.memory}</dd></div>
      </dl>`;
    dom.profilePanel.innerHTML = `
      <h3 class="profile-name">${hiddenName}</h3>
      <p class="profile-desc">${quizActive ? "Algorithm hidden — watch the animation and guess!" : profile.description}</p>
      ${gridHtml}
    `;
    if (quizActive) {
      dom.panePrimaryLabel.textContent = "???";
    } else {
      dom.panePrimaryLabel.textContent = profile.name;
    }
    if (dom.learningCard) dom.learningCard.hidden = quizActive;
    if (dom.learningCardsPanel) dom.learningCardsPanel.hidden = quizActive;
  }

  updateLearningCard() {
    const card = LEARNING_CARDS[dom.algorithm.value];
    if (!card) return;
    dom.learningTrivia.textContent = card.trivia;
    dom.learningUseCase.textContent = card.useCase;
    dom.learningCard.classList.remove("flipped");
  }

  flipLearningCard() {
    dom.learningCard.classList.toggle("flipped");
  }

  loadQuizScore() {
    try {
      const raw = localStorage.getItem(QUIZ_SCORE_KEY);
      return raw ? JSON.parse(raw) : { correct: 0, total: 0 };
    } catch {
      return { correct: 0, total: 0 };
    }
  }

  saveQuizScore() {
    localStorage.setItem(QUIZ_SCORE_KEY, JSON.stringify(this.quizScore));
    this.updateQuizScoreDisplay();
  }

  updateQuizScoreDisplay() {
    dom.quizScore.textContent = `Score: ${this.quizScore.correct} / ${this.quizScore.total}`;
  }

  updateRecommender() {
    if (!this.baseArray.length) {
      dom.recommenderContent.innerHTML = '<p class="recommender-reason">Generate a dataset to see recommendations.</p>';
      return;
    }

    const pick = recommendAlgorithm(this.baseArray);
    const profile = ALGORITHM_PROFILES[pick.algorithm];
    const { stats } = pick;

    dom.recommenderContent.innerHTML = `
      <p class="recommender-pick">${profile.name}</p>
      <p class="recommender-reason">${pick.reason}</p>
      <div class="recommender-stats">
        <span class="recommender-stat">Sortedness: <strong>${Math.round(stats.sortedness * 100)}%</strong></span>
        <span class="recommender-stat">Unique: <strong>${stats.unique}</strong></span>
        <span class="recommender-stat">n: <strong>${stats.n}</strong></span>
      </div>
    `;
  }

  renderCountingArray(count, min, max, activeBucket = -1) {
    const maxCount = Math.max(...count, 1);
    dom.countingArrayPanel.classList.remove("hidden");
    dom.countingArrayDisplay.innerHTML = "";

    for (let v = min; v <= max; v++) {
      const idx = v - min;
      const cell = document.createElement("div");
      cell.className = "counting-cell";

      const bar = document.createElement("div");
      bar.className = `counting-bar ${idx === activeBucket ? "active" : "inactive"}`;
      bar.style.height = `${Math.max(8, (count[idx] / maxCount) * 40)}px`;

      const label = document.createElement("span");
      label.className = "counting-label";
      label.textContent = v;

      const value = document.createElement("span");
      value.className = "counting-value";
      value.textContent = count[idx];

      cell.appendChild(bar);
      cell.appendChild(label);
      cell.appendChild(value);
      dom.countingArrayDisplay.appendChild(cell);
    }
  }

  hideCountingArrayPanel() {
    dom.countingArrayPanel.classList.add("hidden");
    dom.countingArrayDisplay.innerHTML = "";
  }

  buildShareUrl() {
    const params = new URLSearchParams();
    params.set("algo", dom.algorithm.value);
    params.set("dataset", dom.dataset.value);
    params.set("size", dom.size.value);
    params.set("speed", dom.speed.value);
    if (dom.raceMode.checked) {
      params.set("race", "1");
      params.set("raceAlgo", dom.algorithmRace.value);
    }
    if (dom.stepMode.checked) params.set("step", "1");
    if (dom.teachingMode.checked) params.set("teach", "1");
    if (dom.quizMode.checked) params.set("quiz", "1");
    if (dom.dataset.value === "custom" && dom.customArray.value.trim()) {
      params.set("data", dom.customArray.value.trim());
    }
    return `${window.location.origin}${window.location.pathname}?${params.toString()}`;
  }

  loadFromUrl() {
    const params = new URLSearchParams(window.location.search);
    if (!params.toString()) return;

    if (params.has("algo") && ALGORITHM_PROFILES[params.get("algo")]) {
      dom.algorithm.value = params.get("algo");
    }
    if (params.has("dataset") && DATASET_LABELS[params.get("dataset")]) {
      dom.dataset.value = params.get("dataset");
    }
    if (params.has("size")) {
      dom.size.value = params.get("size");
      dom.sizeValue.textContent = params.get("size");
    }
    if (params.has("speed")) {
      dom.speed.value = params.get("speed");
      dom.speedValue.textContent = params.get("speed");
    }
    if (params.get("race") === "1") {
      dom.raceMode.checked = true;
      if (params.has("raceAlgo") && ALGORITHM_PROFILES[params.get("raceAlgo")]) {
        dom.algorithmRace.value = params.get("raceAlgo");
      }
    }
    dom.stepMode.checked = params.get("step") === "1";
    dom.teachingMode.checked = params.get("teach") === "1";
    dom.quizMode.checked = params.get("quiz") === "1";
    if (params.has("data")) {
      dom.dataset.value = "custom";
      dom.customArray.value = params.get("data");
    }
  }

  async copyShareUrl() {
    const url = this.buildShareUrl();
    try {
      await navigator.clipboard.writeText(url);
      this.showToast("Share URL copied");
    } catch {
      this.showToast("Copy failed");
    }
  }

  enterPresentation() {
    this.presentationActive = true;
    dom.presentationOverlay.classList.remove("hidden");
    document.body.classList.add("presentation-active");
    this.initPresentationBars();
    this.syncPresentation();
  }

  exitPresentation() {
    this.presentationActive = false;
    dom.presentationOverlay.classList.add("hidden");
    document.body.classList.remove("presentation-active");
    dom.presentationVisualizer.innerHTML = "";
    dom.presentationHeatmap.innerHTML = "";
    this.presentationBars = [];
    this.presentationHeatmapCells = [];
  }

  initPresentationBars() {
    const n = this.primary.array.length;
    dom.presentationVisualizer.innerHTML = "";
    dom.presentationHeatmap.innerHTML = "";
    this.presentationBars = [];
    this.presentationHeatmapCells = [];

    for (let i = 0; i < n; i++) {
      const bar = document.createElement("div");
      bar.className = "bar";
      dom.presentationVisualizer.appendChild(bar);
      this.presentationBars.push(bar);

      const cell = document.createElement("div");
      cell.className = "heatmap-cell";
      dom.presentationHeatmap.appendChild(cell);
      this.presentationHeatmapCells.push(cell);
    }
  }

  syncPresentation(runner = this.primary) {
    if (!this.presentationActive) return;

    const profile = ALGORITHM_PROFILES[dom.algorithm.value];
    const quizActive = dom.quizMode.checked && this.isRunning;
    dom.presentationAlgo.textContent = quizActive ? "???" : profile.name;

    const m = runner.metrics;
    dom.presentationMetrics.textContent = `${m.comparisons} cmp · ${m.swaps} swp · ${m.writes} wrt · ${m.elapsedMs} ms`;

    if (this.presentationBars.length !== runner.array.length) {
      this.initPresentationBars();
    }

    const stateClasses = ["compare", "swap", "sorted", "pivot", "write", "digit", "gap", "bucket"];
    const maxAccess = Math.max(...runner.accessCounts, 1);

    runner.array.forEach((value, i) => {
      const bar = this.presentationBars[i];
      const heatCell = this.presentationHeatmapCells[i];
      const sourceBar = runner.bars[i];

      if (bar) {
        bar.style.height = `${value}%`;
        stateClasses.forEach((cls) => bar.classList.toggle(cls, sourceBar?.classList.contains(cls)));
        if (runner.identityColors) {
          bar.style.setProperty("--bar-identity", runner.identityHue(runner.ids[i]));
          bar.classList.add("identity");
        } else {
          bar.style.removeProperty("--bar-identity");
          bar.classList.remove("identity");
        }
        bar.textContent = runner.array.length <= 24 ? String(value) : "";
      }
      if (heatCell) {
        heatCell.style.background = heatmapColor((runner.accessCounts[i] || 0) / maxAccess);
      }
    });
  }

  showQuizPanel(correctAlgorithm) {
    this.quizAnswer = correctAlgorithm;
    dom.quizPanel.hidden = false;
    dom.quizFeedback.textContent = "";
    dom.quizGuessGrid.innerHTML = "";

    ALGORITHM_IDS.forEach((id) => {
      const btn = document.createElement("button");
      btn.type = "button";
      btn.className = "quiz-guess-btn";
      btn.textContent = ALGORITHM_PROFILES[id].name;
      btn.addEventListener("click", () => this.handleQuizGuess(id, btn));
      dom.quizGuessGrid.appendChild(btn);
    });
  }

  handleQuizGuess(guess, btn) {
    if (!this.quizAnswer) return;

    const correct = guess === this.quizAnswer;
    this.quizScore.total++;
    if (correct) this.quizScore.correct++;
    this.saveQuizScore();

    dom.quizGuessGrid.querySelectorAll(".quiz-guess-btn").forEach((b) => {
      b.disabled = true;
      const id = ALGORITHM_IDS.find((aid) => ALGORITHM_PROFILES[aid].name === b.textContent);
      if (id === this.quizAnswer) b.classList.add("correct");
      else if (b === btn) b.classList.add("wrong");
    });

    const answerName = ALGORITHM_PROFILES[this.quizAnswer].name;
    dom.quizFeedback.textContent = correct
      ? `✓ Correct — it was ${answerName}!`
      : `✗ Not quite — it was ${answerName}.`;
    dom.quizFeedback.style.color = correct ? "var(--bar-sorted)" : "var(--bar-swap)";

    this.updateProfile();
    this.announce(correct ? "Quiz answer correct." : `Quiz answer incorrect. It was ${answerName}.`);
  }

  setControlsDisabled(disabled) {
    const ids = [
      "algorithm", "algorithmRace", "dataset", "size", "speed",
      "raceMode", "stepMode", "teachingMode", "quizMode", "generateBtn", "startBtn",
      "resetBtn", "tournamentBtn", "applyCustomBtn", "shareUrlBtn", "presentationBtn",
    ];
    ids.forEach((id) => {
      const el = dom[id];
      if (el) el.disabled = disabled;
    });
    dom.algorithmRace.disabled = disabled || !dom.raceMode.checked;
    dom.pauseBtn.disabled = !disabled;
    dom.stopBtn.disabled = !disabled;
    dom.nextStepBtn.disabled = !disabled || !dom.stepMode.checked;
    if (dom.dataset.value === "custom") dom.size.disabled = true;
  }

  identityColorsEnabled() {
    return !!(dom.identityColors && dom.identityColors.checked);
  }

  syncIdentityColors() {
    const on = this.identityColorsEnabled();
    this.primary.identityColors = on;
    this.secondary.identityColors = on;
    this.primary.applyBarStyles();
    this.secondary.applyBarStyles();
    this.syncPresentation();
  }

  configureRunners({ silent = false } = {}) {
    const teaching = dom.teachingMode.checked;
    const config = {
      audio: silent ? null : this.audio,
      speedSlider: dom.speed,
      stepMode: dom.stepMode.checked,
      silent,
      teachingMode: teaching,
      identityColors: this.identityColorsEnabled(),
      onNarrate: (msg) => this.setTeaching(msg),
      onOperation: silent ? null : (total) => this.opsChart.push(total),
      onVisualUpdate: silent ? null : (runner) => {
        if (runner === this.primary) this.syncPresentation(runner);
      },
      onCountingArrayUpdate: silent
        ? null
        : (count, min, max, activeBucket) => this.renderCountingArray(count, min, max, activeBucket),
    };
    this.primary.configure(config);
    this.secondary.configure({ ...config, onOperation: null, onCountingArrayUpdate: null });
    this.primary.paused = false;
    this.secondary.paused = false;
    this.primary.stopped = false;
    this.secondary.stopped = false;
  }

  async startSort() {
    if (this.isRunning) return;

    this.isRunning = true;
    this.setControlsDisabled(true);
    this.opsChart.reset();
    this.configureRunners();

    const algoPrimary = dom.algorithm.value;
    const algoRace = dom.algorithmRace.value;
    const dataset = dom.dataset.value;
    const size = this.baseArray.length;
    const racing = dom.raceMode.checked;
    const quizActive = dom.quizMode.checked && !racing;

    if (quizActive) {
      dom.quizPanel.hidden = true;
      dom.quizFeedback.textContent = "";
      this.updateProfile();
    }

    this.secondary.setArray(this.baseArray);
    this.primary.setArray(this.baseArray);
    this.hideCountingArrayPanel();

    if (algoPrimary === "counting") {
      dom.countingArrayPanel.classList.remove("hidden");
    }

    const statusMsg = racing
      ? `Racing ${ALGORITHM_PROFILES[algoPrimary].name} vs ${ALGORITHM_PROFILES[algoRace].name}…`
      : quizActive
        ? "Running sort — watch closely and guess the algorithm…"
        : `Running ${ALGORITHM_PROFILES[algoPrimary].name}…`;
    this.setStatus(statusMsg);
    this.announce(statusMsg);
    this.syncPresentation();

    try {
      if (racing) {
        await Promise.all([
          this.primary.run(algoPrimary),
          this.secondary.run(algoRace),
        ]);
      } else {
        await this.primary.run(algoPrimary);
      }

      this.recordRun({
        timestamp: new Date().toISOString(),
        mode: racing ? "race" : quizActive ? "quiz" : "single",
        dataset,
        datasetLabel: DATASET_LABELS[dataset],
        size,
        primary: {
          algorithm: algoPrimary,
          name: ALGORITHM_PROFILES[algoPrimary].name,
          ...this.pickMetrics(this.primary.metrics),
        },
        secondary: racing
          ? {
              algorithm: algoRace,
              name: ALGORITHM_PROFILES[algoRace].name,
              ...this.pickMetrics(this.secondary.metrics),
            }
          : null,
      });

      if (quizActive) {
        this.showQuizPanel(algoPrimary);
        this.setStatus("Sort complete — which algorithm was that?");
        this.announce("Sort complete. Guess the algorithm.");
      } else {
        this.setStatus("Sort complete");
        this.announce("Sort complete.");
        this.updateProfile();
      }
    } catch {
      this.setStatus("Sort stopped");
      this.announce("Sort stopped.");
      this.updateProfile();
    } finally {
      this.isRunning = false;
      this.primary.paused = false;
      this.secondary.paused = false;
      this.hideCountingArrayPanel();
      this.setControlsDisabled(false);
      this.updateCustomFieldVisibility();
      this.syncPresentation();
    }
  }

  async runTournament() {
    if (this.isRunning) return;

    this.isRunning = true;
    this.setControlsDisabled(true);
    this.opsChart.reset();

    const data = [...this.baseArray];
    const dataset = dom.dataset.value;
    const size = data.length;
    const results = [];

    this.setStatus("Running benchmark tournament on all 16 algorithms…");
    this.announce("Benchmark tournament started.");

    const useCore = typeof SortCore !== "undefined";

    for (const algo of ALGORITHM_IDS) {
      this.setStatus(`Tournament: running ${ALGORITHM_PROFILES[algo].name}…`);
      let metrics;
      if (useCore) {
        const t0 = performance.now();
        const result = SortCore.sort(algo, data);
        metrics = {
          comparisons: result.comparisons,
          swaps: result.swaps,
          writes: result.writes,
          elapsedMs: Math.round(performance.now() - t0),
        };
        await new Promise((r) => setTimeout(r, 0));
      } else {
        this.configureRunners({ silent: true });
        this.primary.setArray(data);
        await this.primary.run(algo);
        metrics = this.pickMetrics(this.primary.metrics);
      }
      results.push({
        algorithm: algo,
        name: ALGORITHM_PROFILES[algo].name,
        theoretical: ALGORITHM_PROFILES[algo].avg,
        ...metrics,
      });
    }

    results.sort((a, b) => a.elapsedMs - b.elapsedMs || a.comparisons - b.comparisons);
    this.lastTournamentResults = results;
    this.renderLeaderboard(results);
    this.renderComparisonMatrix(results);
    dom.tournamentPanel.hidden = false;
    dom.comparisonPanel.hidden = false;

    this.recordRun({
      timestamp: new Date().toISOString(),
      mode: "tournament",
      dataset,
      datasetLabel: DATASET_LABELS[dataset],
      size,
      primary: {
        algorithm: "tournament",
        name: `Tournament winner: ${results[0].name}`,
        ...results[0],
      },
      secondary: null,
      tournamentResults: results,
    });

    const winnerMsg = `Tournament complete — 🏆 ${results[0].name} (${results[0].elapsedMs} ms)`;
    this.setStatus(winnerMsg);
    this.announce(winnerMsg);
    this.showToast("Tournament complete");

    this.isRunning = false;
    this.setControlsDisabled(false);
    this.updateCustomFieldVisibility();
  }

  renderLeaderboard(results) {
    dom.leaderboard.innerHTML = `
      <table class="data-table">
        <thead>
          <tr>
            <th>Rank</th>
            <th>Algorithm</th>
            <th>Time (ms)</th>
            <th>Comparisons</th>
            <th>Swaps</th>
          </tr>
        </thead>
        <tbody>
          ${results
            .map(
              (r, i) => `
            <tr class="rank-${i + 1}">
              <td>${i + 1}</td>
              <td>${r.name}</td>
              <td>${r.elapsedMs}</td>
              <td>${r.comparisons}</td>
              <td>${r.swaps}</td>
            </tr>`
            )
            .join("")}
        </tbody>
      </table>
    `;
  }

  assessFit(result, n) {
    const profile = ALGORITHM_PROFILES[result.algorithm];
    const n2 = n * n;
    const nlogn = n * Math.log2(Math.max(n, 2));

    let expected;
    if (profile.avg.includes("n²") || profile.avg.includes("n^2")) {
      expected = n2;
    } else if (profile.avg.includes("log")) {
      expected = nlogn;
    } else if (profile.avg.includes("nk") || result.algorithm === "radix" || result.algorithm === "counting") {
      expected = n * 3;
    } else {
      expected = n;
    }

    const ratio = result.comparisons / expected;
    if (ratio < 1.5) return { class: "match-good", label: "As expected" };
    if (ratio < 4) return { class: "match-warn", label: "Moderate" };
    return { class: "", label: "Heavy ops" };
  }

  renderComparisonMatrix(results) {
    const n = this.baseArray.length;
    dom.comparisonMatrix.innerHTML = `
      <table class="data-table">
        <thead>
          <tr>
            <th>Algorithm</th>
            <th>Theoretical (avg)</th>
            <th>Actual comparisons</th>
            <th>Time (ms)</th>
            <th>Fit</th>
          </tr>
        </thead>
        <tbody>
          ${results
            .map((r) => {
              const fit = this.assessFit(r, n);
              return `
            <tr>
              <td>${r.name}</td>
              <td>${r.theoretical}</td>
              <td>${r.comparisons}</td>
              <td>${r.elapsedMs}</td>
              <td class="${fit.class}">${fit.label}</td>
            </tr>`;
            })
            .join("")}
        </tbody>
      </table>
    `;
  }

  pickMetrics(metrics) {
    return {
      comparisons: metrics.comparisons,
      swaps: metrics.swaps,
      writes: metrics.writes,
      elapsedMs: metrics.elapsedMs,
    };
  }

  togglePause() {
    if (!this.isRunning || dom.stepMode.checked) return;
    this.primary.paused = !this.primary.paused;
    this.secondary.paused = this.primary.paused;
    dom.pauseBtn.textContent = this.primary.paused ? "Resume" : "Pause";
    const msg = this.primary.paused ? "Paused — Space to resume" : "Running…";
    this.setStatus(msg);
    this.announce(msg);
  }

  stopSort() {
    if (!this.isRunning) return;
    this.primary.stopped = true;
    this.secondary.stopped = true;
    this.primary.paused = false;
    this.secondary.paused = false;
    this.primary.resolveStep();
    this.secondary.resolveStep();
    dom.pauseBtn.textContent = "Pause";
    this.setStatus("Stopping…");
    this.announce("Stopping sort.");
  }

  nextStep() {
    this.primary.resolveStep();
    this.secondary.resolveStep();
  }

  recordRun(entry) {
    this.lastRunSummary = entry;
    this.history.unshift(entry);
    this.history = this.history.slice(0, MAX_HISTORY);
    localStorage.setItem(HISTORY_KEY, JSON.stringify(this.history));
    this.renderHistory();
  }

  loadHistory() {
    try {
      const raw = localStorage.getItem(HISTORY_KEY);
      return raw ? JSON.parse(raw) : [];
    } catch {
      return [];
    }
  }

  renderHistory() {
    if (!this.history.length) {
      dom.historyList.innerHTML = '<li class="history-empty">No runs yet</li>';
      return;
    }

    dom.historyList.innerHTML = this.history
      .map((run) => {
        const date = new Date(run.timestamp).toLocaleString();
        const primaryLine = `${run.primary.name}: ${run.primary.comparisons}c / ${run.primary.swaps}s / ${run.primary.elapsedMs}ms`;
        const secondaryLine = run.secondary
          ? `<span class="history-secondary">${run.secondary.name}: ${run.secondary.comparisons}c / ${run.secondary.swaps}s / ${run.secondary.elapsedMs}ms</span>`
          : "";
        return `
          <li class="history-item">
            <span class="history-meta">${date} · ${run.datasetLabel} · n=${run.size} · ${run.mode}</span>
            <span class="history-primary">${primaryLine}</span>
            ${secondaryLine}
          </li>
        `;
      })
      .join("");
  }

  buildCsv() {
    const header = [
      "timestamp",
      "mode",
      "dataset",
      "size",
      "algorithm",
      "comparisons",
      "swaps",
      "writes",
      "elapsed_ms",
      "pane",
    ];

    const rows = [header.join(",")];

    this.history.forEach((run) => {
      rows.push(
        [
          run.timestamp,
          run.mode,
          run.dataset,
          run.size,
          run.primary.algorithm,
          run.primary.comparisons,
          run.primary.swaps,
          run.primary.writes,
          run.primary.elapsedMs,
          "primary",
        ].join(",")
      );

      if (run.secondary) {
        rows.push(
          [
            run.timestamp,
            run.mode,
            run.dataset,
            run.size,
            run.secondary.algorithm,
            run.secondary.comparisons,
            run.secondary.swaps,
            run.secondary.writes,
            run.secondary.elapsedMs,
            "secondary",
          ].join(",")
        );
      }

      if (run.tournamentResults) {
        run.tournamentResults.forEach((r) => {
          rows.push(
            [
              run.timestamp,
              "tournament",
              run.dataset,
              run.size,
              r.algorithm,
              r.comparisons,
              r.swaps,
              r.writes,
              r.elapsedMs,
              "tournament",
            ].join(",")
          );
        });
      }
    });

    return rows.join("\n");
  }

  exportCsv() {
    const csv = this.buildCsv();
    const blob = new Blob([csv], { type: "text/csv;charset=utf-8;" });
    const url = URL.createObjectURL(blob);
    const link = document.createElement("a");
    link.href = url;
    link.download = `sort-lab-history-${Date.now()}.csv`;
    link.click();
    URL.revokeObjectURL(url);
    this.showToast("CSV exported");
  }

  buildSummaryText() {
    if (!this.lastRunSummary) {
      return "No completed run to summarize yet.";
    }

    const run = this.lastRunSummary;
    let text = `Sort Lab Run\n`;
    text += `Dataset: ${run.datasetLabel} (n=${run.size})\n`;

    if (run.mode === "tournament" && run.tournamentResults) {
      text += "Tournament results:\n";
      run.tournamentResults.forEach((r, i) => {
        text += `${i + 1}. ${r.name}: ${r.comparisons}c, ${r.swaps}s, ${r.elapsedMs}ms\n`;
      });
      return text;
    }

    text += `${run.primary.name}: ${run.primary.comparisons} comparisons, ${run.primary.swaps} swaps, ${run.primary.writes} writes, ${run.primary.elapsedMs} ms\n`;

    if (run.secondary) {
      text += `${run.secondary.name}: ${run.secondary.comparisons} comparisons, ${run.secondary.swaps} swaps, ${run.secondary.writes} writes, ${run.secondary.elapsedMs} ms\n`;
      const winner =
        run.primary.elapsedMs <= run.secondary.elapsedMs
          ? run.primary.name
          : run.secondary.name;
      text += `Winner (time): ${winner}`;
    }

    return text;
  }

  async copySummary() {
    const text = this.buildSummaryText();
    try {
      await navigator.clipboard.writeText(text);
      this.showToast("Summary copied");
    } catch {
      this.showToast("Copy failed");
    }
  }

  toggleTheme() {
    const current = document.documentElement.getAttribute("data-theme");
    const next = current === "dark" ? "light" : "dark";
    document.documentElement.setAttribute("data-theme", next);
    dom.themeToggle.textContent = next === "dark" ? "☀️" : "🌙";
    dom.themeToggle.setAttribute("aria-pressed", next === "dark");
    localStorage.setItem("theme", next);
    this.opsChart.draw();
    this.primary.renderHeatmap();
    this.secondary.renderHeatmap();
    if (this.presentationActive) this.syncPresentation();
  }

  setStatus(message) {
    dom.statusText.textContent = message;
  }

  setTeaching(message) {
    dom.teachingText.textContent = message;
    this.announce(message);
  }

  announce(message) {
    if (!dom.a11yAnnouncer) return;
    dom.a11yAnnouncer.textContent = "";
    requestAnimationFrame(() => {
      dom.a11yAnnouncer.textContent = message;
    });
  }

  showToast(message) {
    dom.toast.textContent = message;
    dom.toast.classList.add("visible");
    clearTimeout(this.toastTimer);
    this.toastTimer = setTimeout(() => dom.toast.classList.remove("visible"), 2200);
  }
}

// ---------- Boot ----------
const app = new SortLabApp();
app.init();