Merge Sort

// 1) The idea
// • Base case: one-element array is sorted
// • Recursive case: sort left half, sort right half, merge them
// • Merge: walk two sorted arrays with two pointers; pick smaller

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left  = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    const out = new Array(left.length + right.length);
    let i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) out[k++] = left[i++];   // <= keeps STABLE
        else                       out[k++] = right[j++];
    }
    while (i < left.length)  out[k++] = left[i++];
    while (j < right.length) out[k++] = right[j++];
    return out;
}

// 2) Stability
// '<=' in the merge step keeps elements with equal keys in their original order.
// Stability matters when sorting on a secondary key after a primary sort.

// 3) Complexity
// • Time:    O(n log n) — best, average, worst
// • Space:   O(n) auxiliary (the merge buffer)
// • Stable: yes
// • In-place: no (the textbook version)
// • Adaptive: not really (sorted input still does the work)

// 4) Iterative bottom-up version (no recursion)
function mergeSortIterative(arr) {
    const n = arr.length;
    const buf = new Array(n);
    for (let width = 1; width < n; width *= 2) {
        for (let i = 0; i < n; i += 2 * width) {
            const mid = Math.min(i + width, n);
            const right = Math.min(i + 2 * width, n);
            mergeInPlace(arr, buf, i, mid, right);
        }
    }
    return arr;
}

function mergeInPlace(arr, buf, l, m, r) {
    let i = l, j = m, k = l;
    while (i < m && j < r) buf[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i < m) buf[k++] = arr[i++];
    while (j < r) buf[k++] = arr[j++];
    for (let x = l; x < r; x++) arr[x] = buf[x];
}

// 5) Sorting linked lists — merge sort is the right answer
// Quicksort needs random access; merge sort works with sequential walks.
function mergeSortList(head) {
    if (!head || !head.next) return head;
    let slow = head, fast = head, prev = null;
    while (fast && fast.next) { prev = slow; slow = slow.next; fast = fast.next.next; }
    prev.next = null;
    const left  = mergeSortList(head);
    const right = mergeSortList(slow);
    return mergeLists(left, right);
}
function mergeLists(a, b) {
    const dummy = { val: 0, next: null };
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
}

// 6) External sort — too big for memory
// 100 GB file, 4 GB RAM:
//   1. Read 4 GB chunks, sort each in memory, write to disk (25 runs of 4 GB)
//   2. k-way merge those runs using a heap of size k
//   3. Output one final sorted stream
// Used by databases (ORDER BY when work_mem is too small), MapReduce shuffle phase, log indexers.

// 7) Parallel merge sort
// Each recursive call is independent → easy to fork. With p threads:
//   • Time: O(n log n / p)
//   • Work: O(n log n)
// Use thread pools / Web Workers / Goroutines for the recursive split; merge serially.

// 8) Counting inversions — classic interview problem
function countInversions(arr) {
    let count = 0;
    function sort(a) {
        if (a.length <= 1) return a;
        const mid = Math.floor(a.length / 2);
        const L = sort(a.slice(0, mid));
        const R = sort(a.slice(mid));
        let i = 0, j = 0, out = [];
        while (i < L.length && j < R.length) {
            if (L[i] <= R[j]) out.push(L[i++]);
            else { count += L.length - i; out.push(R[j++]); }
        }
        return out.concat(L.slice(i), R.slice(j));
    }
    sort(arr);
    return count;
}

// 9) Comparison to other sorts
//
// Algorithm     Time avg   Time worst   Space   Stable   In-place
// Insertion     O(n²)      O(n²)        O(1)    Yes      Yes        — best on small / nearly sorted
// Quicksort     O(n log n) O(n²)        O(log n) No       Yes        — fast in practice, bad worst case
// Mergesort     O(n log n) O(n log n)   O(n)    Yes      No         — predictable; good for linked lists
// Heapsort      O(n log n) O(n log n)   O(1)    No       Yes        — no extra space; cache-unfriendly
// Timsort       O(n log n) O(n log n)   O(n)    Yes      No         — adaptive; Python/Java sort()
// Radix sort    O(n*k)     O(n*k)       O(n+k)   Depends  No         — integers / fixed-width keys only

// 10) When to choose merge sort
//   ✓ Need a STABLE sort (Java's Arrays.sort for objects uses TimSort = adaptive merge sort)
//   ✓ Sorting linked lists
//   ✓ External sorting on big data
//   ✓ Predictable worst case (real-time systems)
//   ✗ Memory-constrained environments (heapsort or in-place insertion may fit better)
//   ✗ Already-sorted data where adaptive Timsort would skip work

// 11) Real-world stdlib implementations
//   • Python sorted() / list.sort() — TimSort (adaptive merge sort) since 2.3
//   • Java Arrays.sort for OBJECTS — TimSort
//   • Java Arrays.sort for PRIMITIVES — Dual-Pivot Quicksort
//   • JavaScript Array.prototype.sort — ES2019 mandates STABLE; V8 uses TimSort
//   • Rust slice::sort_unstable — pattern-defeating quicksort; sort = merge-based stable
//   • Go sort.Slice — pattern-defeating quicksort (unstable); SortStable = merge sort

// 12) Implementing in-place (advanced)
// True in-place merge sort exists but is complex (Practical In-Place Merge Sort, block merge).
// In practice the O(n) buffer version is simpler and almost always fine.

// 13) Common bugs
// • Using < instead of <= in merge → unstable sort (silently breaks downstream code)
// • Allocating buf inside the recursion → O(n log n) allocations; allocate once at the top
// • Off-by-one in bottom-up bounds — test with arrays of size 1, 2, 3, prime sizes
// • Slicing arr.slice(0, mid) on every recursion → quadratic memory pressure; use indices
// • Stack overflow on huge inputs (deeply recursive) — switch to iterative for n > 10⁶
// • Comparing objects with default < → 'undefined behaviour' for non-primitives in JS; provide a comparator

function mergeSort(a) {
    if (a.length < 2) return a;
    const m = a.length >> 1;
    return merge(mergeSort(a.slice(0, m)), mergeSort(a.slice(m)));
}
function merge(L, R) {
    const out = []; let i = 0, j = 0;
    while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++]);
    return out.concat(L.slice(i)).concat(R.slice(j));
}