// ─────────────────────────────────────────────────────────────────────────────
// SORTING
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : comparison sorts (n log n floor) vs non-comparison sorts (linear on constrained keys).
// TELL   : "kth smallest/largest" (quickselect), "small integer range" (counting), "nearly sorted"
//          (insertion), "stable" (merge/TimSort), "in place O(1) space" (heap/quick), "top N".
// SAY    : comparator, stable, in-place, divide and conquer, pivot, partition (Lomuto / Hoare),
//          quickselect, counting sort, bucket sort, heapify, TimSort.
// BIG-O  : merge/heap O(n log n) always; quick O(n log n) avg O(n^2) worst; counting O(n + k).
// NOTE   : Array.prototype.sort is TimSort in V8 (stable since ES2019). Default comparator is STRING order:
//          [10, 9, 1].sort() -> [1, 10, 9]. Always pass (a, b) => a - b for numbers.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Comparator recap  —  negative => a first; zero => keep order (stable); positive => b first
assert.deepEqual([10, 9, 1].sort(), [1, 10, 9]); // the trap
assert.deepEqual([10, 9, 1].sort((a, b) => a - b), [1, 9, 10]); // numbers asc
assert.deepEqual([10, 9, 1].sort((a, b) => b - a), [10, 9, 1]); // desc
assert.deepEqual(['b', 'a', 'C'].sort((a, b) => a.localeCompare(b)), ['a', 'b', 'C']); // strings, locale-aware
assert.deepEqual(['b', 'a', 'C'].sort(), ['C', 'a', 'b']); // default: UTF-16 code units
const people = [{ n: 'a', age: 30 }, { n: 'b', age: 25 }, { n: 'c', age: 30 }];
assert.deepEqual( // multi-key: by age desc, then name asc; `||` chains tie-breakers
  people.sort((x, y) => y.age - x.age || x.n.localeCompare(y.n)).map((p) => p.n), ['a', 'c', 'b']);
// stable: equal keys keep input order
assert.deepEqual([{ k: 1, id: 'x' }, { k: 0, id: 'y' }, { k: 1, id: 'z' }].sort((a, b) => a.k - b.k).map((o) => o.id), ['y', 'x', 'z']);

// ── 2. Merge sort  —  split in half, sort each, merge  —  O(n log n) / O(n), stable
function mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const L = mergeSort(a.slice(0, mid)), R = mergeSort(a.slice(mid));
  const out = [];
  let i = 0, j = 0;
  while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]); // <= keeps stability
  return out.concat(L.slice(i), R.slice(j));
}
assert.deepEqual(mergeSort([5, 2, 4, 6, 1, 3]), [1, 2, 3, 4, 5, 6]);
assert.deepEqual(mergeSort([-1, -5, 0]), [-5, -1, 0]);
assert.deepEqual(mergeSort([]), []);

// ── 3. Quick sort  —  partition around pivot, recurse both sides  —  O(n log n) avg, O(n^2) worst / O(log n) stack, not stable
//        Lomuto: pivot at end, single scan, returns pivot's final index. (implemented below)
//        Hoare : pivots in middle, two pointers converge, returns split point (not pivot index); fewer swaps.
function lomuto(a, lo, hi) {
  const p = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) if (a[j] < p) { [a[i], a[j]] = [a[j], a[i]]; i++; }
  [a[i], a[hi]] = [a[hi], a[i]];
  return i;
}
function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  // random pivot swap defends against sorted-input O(n^2)
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];
  const p = lomuto(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
  return a;
}
assert.deepEqual(quickSort([3, 6, 1, 8, 2, 9, 2]), [1, 2, 2, 3, 6, 8, 9]);
assert.deepEqual(quickSort([1]), [1]);
assert.deepEqual(quickSort([]), []);

// ── 4. Quickselect (kth smallest, 0-indexed)  —  partition once, recurse into ONE side  —  O(n) avg, O(n^2) worst / O(1)
function quickselect(a, k) {
  a = [...a];
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const r = lo + Math.floor(Math.random() * (hi - lo + 1));
    [a[r], a[hi]] = [a[hi], a[r]];
    const p = lomuto(a, lo, hi);
    if (p === k) return a[p];
    if (p < k) lo = p + 1; else hi = p - 1;
  }
  return undefined;
}
const kthLargest = (a, k) => quickselect(a, a.length - k);
assert.equal(quickselect([3, 2, 1, 5, 6, 4], 1), 2);
assert.equal(kthLargest([3, 2, 1, 5, 6, 4], 2), 5);
assert.equal(kthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), 4); // duplicates

// ── 5. Counting sort  —  count[v - min]++, then emit  —  O(n + k) / O(k), stable with prefix-sum variant
function countingSort(a) {
  if (a.length === 0) return [];
  const min = Math.min(...a), max = Math.max(...a);
  const count = new Array(max - min + 1).fill(0);
  for (const x of a) count[x - min]++;
  const out = [];
  for (let v = 0; v < count.length; v++) for (let c = 0; c < count[v]; c++) out.push(v + min);
  return out;
}
assert.deepEqual(countingSort([4, 2, 2, 8, 3, 3, 1]), [1, 2, 2, 3, 3, 4, 8]);
assert.deepEqual(countingSort([-2, 0, -2]), [-2, -2, 0]);
assert.deepEqual(countingSort([]), []);

// ── 6. Bucket sort  —  distribute into k buckets by value range, sort each, concat  —  O(n + k) avg / O(n)
function bucketSort(a, k = 5) {
  if (a.length === 0) return [];
  const min = Math.min(...a), max = Math.max(...a), span = (max - min) / k || 1;
  const buckets = Array.from({ length: k }, () => []);
  for (const x of a) buckets[Math.min(k - 1, Math.floor((x - min) / span))].push(x);
  return buckets.flatMap((b) => b.sort((x, y) => x - y));
}
assert.deepEqual(bucketSort([0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]), [0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52]);
assert.deepEqual(bucketSort([5, 5, 5]), [5, 5, 5]);

// ── 7. Heap sort sketch  —  heapify (O(n)), then repeatedly swap root to end + sift down  —  O(n log n) / O(1), not stable
function heapSort(a) {
  const n = a.length;
  const sift = (i, size) => {
    for (;;) {
      let big = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < size && a[l] > a[big]) big = l;
      if (r < size && a[r] > a[big]) big = r;
      if (big === i) return;
      [a[i], a[big]] = [a[big], a[i]];
      i = big;
    }
  };
  for (let i = (n >> 1) - 1; i >= 0; i--) sift(i, n); // build max-heap bottom-up
  for (let end = n - 1; end > 0; end--) { [a[0], a[end]] = [a[end], a[0]]; sift(0, end); }
  return a;
}
assert.deepEqual(heapSort([5, 3, 8, 1, 9, 2]), [1, 2, 3, 5, 8, 9]);
assert.deepEqual(heapSort([2, 2, 1]), [1, 2, 2]);
assert.deepEqual(heapSort([]), []);

// ── 8. Insertion sort  —  grow a sorted prefix; shift larger elements right  —  O(n^2) worst, O(n) nearly sorted / O(1), stable
//        SAY: used for small n (TimSort/introsort switch to it under ~32) and for online / nearly-sorted input.
function insertionSort(a) {
  for (let i = 1; i < a.length; i++) {
    const x = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; }
    a[j + 1] = x;
  }
  return a;
}
assert.deepEqual(insertionSort([4, 3, 2, 10, 12, 1, 5, 6]), [1, 2, 3, 4, 5, 6, 10, 12]);
assert.deepEqual(insertionSort([1, 2, 3]), [1, 2, 3]);
assert.deepEqual(insertionSort([]), []);

// ── 9. When to choose which
//   need stable + guaranteed n log n  -> merge sort (or built-in sort)
//   in-place, avg fast, cache-friendly -> quick sort (random pivot)
//   guaranteed n log n + O(1) space    -> heap sort
//   small integer keys, range k ~ n    -> counting / radix
//   uniform floats in [0,1)            -> bucket
//   n < ~32 or nearly sorted           -> insertion
//   kth element only                   -> quickselect (or heap of size k: O(n log k))

// ── 10. Sort by custom key then slice (top-N)  —  O(n log n); for large n prefer heap O(n log N)
const topN = (arr, n, key) => [...arr].sort((a, b) => key(b) - key(a)).slice(0, n);
assert.deepEqual(topN([{ s: 3 }, { s: 9 }, { s: 5 }], 2, (o) => o.s), [{ s: 9 }, { s: 5 }]);
assert.deepEqual(topN([], 2, (o) => o.s), []);

// ── 11. Sort colors (Dutch national flag)  —  3-way partition in one pass  —  O(n) / O(1)
function sortColors(a) {
  let lo = 0, mid = 0, hi = a.length - 1;
  while (mid <= hi) {
    if (a[mid] === 0) [a[lo++], a[mid++]] = [a[mid], a[lo]];
    else if (a[mid] === 2) [a[mid], a[hi--]] = [a[hi], a[mid]];
    else mid++;
  }
  return a;
}
assert.deepEqual(sortColors([2, 0, 2, 1, 1, 0]), [0, 0, 1, 1, 2, 2]);
assert.deepEqual(sortColors([1]), [1]);

// ── 12. Merge intervals (sorting application)  —  sort by start; extend last if overlapping  —  O(n log n) / O(n)
function mergeIntervals(iv) {
  iv = [...iv].sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of iv) {
    if (out.length && s <= out[out.length - 1][1]) out[out.length - 1][1] = Math.max(out[out.length - 1][1], e);
    else out.push([s, e]);
  }
  return out;
}
assert.deepEqual(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]), [[1, 6], [8, 10], [15, 18]]);
assert.deepEqual(mergeIntervals([[1, 4], [4, 5]]), [[1, 5]]);
assert.deepEqual(mergeIntervals([]), []);

console.log('ok: algorithms/sorting.js');