// ─────────────────────────────────────────────────────────────────────────────
// JS SORTING — the #1 silent bug in JS interviews
// ─────────────────────────────────────────────────────────────────────────────
// RULE    : sort() with NO comparator converts to STRINGS. Always pass one.
// MUTATES : sort() and reverse() change the array in place and return it.
// STABLE  : since ES2019 (TimSort). Equal elements keep input order.
// SAY     : "comparator", "stable sort", "multi-key / tie-breaker", "O(n log n)",
//           "sort then slice for top-N", "localeCompare for strings"
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Numbers
assert.deepEqual([10, 9, 1, 100].sort(), [1, 10, 100, 9]);                 // WRONG: "1" < "10" < "100" < "9"
assert.deepEqual([10, 9, 1, 100].sort((a, b) => a - b), [1, 9, 10, 100]);  // ascending
assert.deepEqual([10, 9, 1, 100].sort((a, b) => b - a), [100, 10, 9, 1]);  // descending
// comparator contract: negative -> a first, positive -> b first, 0 -> keep order

// ── 2. Don't destroy the input
const original = [3, 1, 2];
const sorted = [...original].sort((a, b) => a - b);          // Node 20+: original.toSorted(cmp)
assert.deepEqual(original, [3, 1, 2]);
assert.deepEqual(sorted, [1, 2, 3]);

// ── 3. Strings
assert.deepEqual(['b', 'a', 'C'].sort(), ['C', 'a', 'b']);                        // char codes: uppercase first
assert.deepEqual(['b', 'a', 'C'].sort((x, y) => x.localeCompare(y)), ['a', 'b', 'C']);
assert.deepEqual(['b', 'a', 'C'].sort((x, y) => (x < y ? -1 : x > y ? 1 : 0)), ['C', 'a', 'b']);  // explicit ASCII
assert.deepEqual(['item10', 'item2'].sort((x, y) => x.localeCompare(y, undefined, { numeric: true })), ['item2', 'item10']);

// ── 4. Multi-key with tie-breakers: chain with ||  (0 is falsy, so it falls through)
const people = [
  { name: 'bo', score: 90, age: 30 },
  { name: 'al', score: 90, age: 25 },
  { name: 'cy', score: 95, age: 40 },
];
people.sort((p, q) => q.score - p.score || p.name.localeCompare(q.name));   // score desc, then name asc
assert.deepEqual(people.map(p => p.name), ['cy', 'al', 'bo']);
people.sort((p, q) => p.age - q.age);
assert.deepEqual(people.map(p => p.name), ['al', 'bo', 'cy']);

// ── 5. Sort by a derived key (compute once: "Schwartzian transform" / decorate-sort-undecorate)
const words = ['banana', 'fig', 'apple'];
const byLenThenAlpha = words
  .map(w => ({ w, k: w.length }))
  .sort((x, y) => x.k - y.k || x.w.localeCompare(y.w))
  .map(x => x.w);
assert.deepEqual(byLenThenAlpha, ['fig', 'apple', 'banana']);

// ── 6. Booleans / custom order / Map entries
assert.deepEqual([true, false, true].sort((x, y) => Number(y) - Number(x)), [true, true, false]);
const priority = { high: 0, medium: 1, low: 2 };
assert.deepEqual(['low', 'high', 'medium'].sort((x, y) => priority[x] - priority[y]), ['high', 'medium', 'low']);
const counts = new Map([['b', 2], ['a', 2], ['c', 5]]);
assert.deepEqual([...counts].sort(([k1, v1], [k2, v2]) => v2 - v1 || k1.localeCompare(k2)), [['c', 5], ['a', 2], ['b', 2]]);

// ── 7. Top-N / Kth
assert.deepEqual([5, 1, 4, 2, 3].sort((a, b) => b - a).slice(0, 2), [5, 4]);
assert.equal([5, 1, 4, 2, 3].sort((a, b) => a - b)[1], 2);   // 2nd smallest (quickselect is O(n) if asked)

// ── 8. Stability demo
const stable = [{ k: 1, v: 'x' }, { k: 0, v: 'y' }, { k: 1, v: 'z' }].sort((a, b) => a.k - b.k);
assert.deepEqual(stable.map(o => o.v), ['y', 'x', 'z']);      // x stays before z

// ── 9. Sorting numbers stored as strings / mixed
assert.deepEqual(['10', '9', '1'].sort((a, b) => Number(a) - Number(b)), ['1', '9', '10']);
assert.deepEqual([3, '2', 1].sort((a, b) => a - b), [1, '2', 3]);  // coercion in subtraction, fine here

// ── 10. Check "is sorted" in one pass
const isSorted = xs => xs.every((x, i) => i === 0 || xs[i - 1] <= x);
assert.equal(isSorted([1, 2, 2, 3]), true);
assert.equal(isSorted([2, 1]), false);

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