function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

function bubbleSortOptimized(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break;  // Early exit — array is sorted
    }
    return arr;
}

Step 1: Sort by salary (any sort)
        [(Alice,$70k), (Bob,$60k), (Carol,$70k), (Dave,$60k)]

Step 2: Sort by department (STABLE sort)
        Engineering: Alice($70k) → Carol($70k) ← salary order preserved ✅
        Sales: Bob($60k) → Dave($60k) ← salary order preserved ✅

function selectionSort(arr) {
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            // This loop ALWAYS runs — even on sorted input
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        // Even if no swap needed, we still did n-i-1 comparisons
        if (minIndex !== i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
}

for (let i = 1; i < n; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {  // ← False immediately on sorted input
        arr[j + 1] = arr[j];          // ← Never executed
        j--;
    }
    arr[j + 1] = key;
}
// Only the outer loop runs: n iterations × O(1) = O(n)

function merge(left, right) {
    const result = [];  // ← This grows to size n in the top-level merge
    // ... merging logic
    return result;
}

Sorted array: [1, 2, 3, 4, 5, 6, 7, 8]
Pivot = last element = 8
Left partition: [1, 2, 3, 4, 5, 6, 7]  (size n-1)
Right partition: []                     (size 0)
Next call: same pattern → n + (n-1) + ... + 1 = O(n²)

Level (from bottom)  Nodes at this level  Work per node  Total work
      0 (leaves)           n/2                O(0)          O(0)
      1                   n/4                O(1)          O(n/4)
      2                   n/8                O(2)          O(2n/8)
      3                  n/16                O(3)          O(3n/16)
      ...                 ...                ...           ...

Total = n × Σ(h=0 to ∞) h / 2^(h+1)
      = n × 1  = O(n)

class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

function sortLinkedList(head) {
    // Base case
    if (!head || !head.next) return head;

    // Find middle (slow/fast pointer)
    let slow = head, fast = head, prev = null;
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;  // Split into two lists

    // Recursively sort both halves
    const left = sortLinkedList(head);
    const right = sortLinkedList(slow);

    // Merge sorted lists
    return mergeLists(left, right);
}

function mergeLists(l1, l2) {
    const dummy = new ListNode(0);
    let current = dummy;

    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    current.next = l1 || l2;
    return dummy.next;
}

function findKthLargest(nums, k) {
    const n = nums.length;
    const targetIndex = n - k;  // Convert to kth smallest (0-indexed)

    function partition(left, right) {
        const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
        const pivot = nums[pivotIndex];

        // Move pivot to end
        [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];

        let storeIndex = left;
        for (let i = left; i < right; i++) {
            if (nums[i] < pivot) {
                [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]];
                storeIndex++;
            }
        }

        [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]];
        return storeIndex;
    }

    function quickSelect(left, right) {
        if (left === right) return nums[left];

        const pivotIndex = partition(left, right);

        if (pivotIndex === targetIndex) {
            return nums[pivotIndex];
        } else if (pivotIndex < targetIndex) {
            return quickSelect(pivotIndex + 1, right);
        } else {
            return quickSelect(left, pivotIndex - 1);
        }
    }

    return quickSelect(0, n - 1);
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2));  // Output: 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4));  // Output: 4

function sortColors(nums) {
    let low = 0;        // Boundary for 0s
    let mid = 0;        // Current element being examined
    let high = nums.length - 1;  // Boundary for 2s

    while (mid <= high) {
        if (nums[mid] === 0) {
            // Swap to the left (0s section)
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++;
            mid++;
        } else if (nums[mid] === 1) {
            // 1 belongs in the middle — just advance
            mid++;
        } else {  // nums[mid] === 2
            // Swap to the right (2s section)
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
            // Don't increment mid — the swapped-in element needs examination
        }
    }

    return nums;
}

console.log(sortColors([2, 0, 2, 1, 1, 0]));
// Output: [0, 0, 1, 1, 2, 2]

Initial: [2, 0, 2, 1, 1, 0]
          ↑               ↑
         low/mid         high

Step 1: nums[mid]=2 → swap with high, high--
         [0, 0, 2, 1, 1, 2]
          ↑            ↑
        low/mid       high

Step 2: nums[mid]=0 → swap with low, low++, mid++
         [0, 0, 2, 1, 1, 2]
             ↑         ↑
            low/mid   high

Step 3: nums[mid]=2 → swap with high, high--
         [0, 0, 2, 1, 1, 2]
                ↑     ↑
               low   high
               mid

Continue until mid > high → [0, 0, 1, 1, 2, 2] ✅

function mergeSortedArrays(arr1, arr2) {
    const result = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            result.push(arr1[i]);
            i++;
        } else {
            result.push(arr2[j]);
            j++;
        }
    }

    // Add remaining elements
    while (i < arr1.length) result.push(arr1[i++]);
    while (j < arr2.length) result.push(arr2[j++]);

    return result;
}

console.log(mergeSortedArrays([1, 3, 5, 7], [2, 4, 6, 8]));
// Output: [1, 2, 3, 4, 5, 6, 7, 8]

console.log(mergeSortedArrays([1, 2, 3], [4, 5, 6]));
// Output: [1, 2, 3, 4, 5, 6]

function mergeInPlace(nums1, m, nums2, n) {
    // Start from the end of both arrays
    let i = m - 1;      // Last element in nums1's actual data
    let j = n - 1;      // Last element in nums2
    let k = m + n - 1;  // Last position in nums1

    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
}

const nums1 = [1, 2, 3, 0, 0, 0];
mergeInPlace(nums1, 3, [2, 5, 6], 3);
console.log(nums1);  // Output: [1, 2, 2, 3, 5, 6]

function countInversions(arr) {
    let count = 0;

    function mergeAndCount(left, right) {
        const result = [];
        let i = 0, j = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result.push(left[i]);
                i++;
            } else {
                // left[i] > right[j] — this is an inversion!
                // All remaining elements in left are > right[j]
                count += left.length - i;
                result.push(right[j]);
                j++;
            }
        }

        return [...result, ...left.slice(i), ...right.slice(j)];
    }

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

    mergeSort([...arr]);
    return count;
}

console.log(countInversions([2, 4, 1, 3, 5]));
// Output: 3
// Inversions: (2,1), (4,1), (4,3)

console.log(countInversions([5, 4, 3, 2, 1]));
// Output: 10  (reverse sorted = max inversions = n(n-1)/2)

TimSort strategy:
├── Divide array into "runs" (natural sorted subsequences)
├── For small runs (< 32 elements):
│   └── Use INSERTION SORT (fast for small n, cache-efficient)
├── For larger runs:
│   └── Use MERGE SORT merging strategy
│       └── Merge non-adjacent runs using "galloping mode"
└── Result: Stable, adaptive, O(n) on sorted data, O(n log n) worst case

IntroSort strategy:
├── Start with QUICK SORT (fast average case)
├── Track recursion depth with a counter
├── If depth exceeds 2 × log₂(n):
│   └── Switch to HEAP SORT (guarantees O(n log n))
└── For small subarrays (< 16 elements):
    └── Switch to INSERTION SORT (low overhead)

Must-Know Facts for Sorting Interviews:

1. Comparison sorts cannot beat O(n log n)  ← Decision tree proof
2. Only non-comparison sorts (Counting, Radix, Bucket) can do O(n)
3. Quick Sort is fastest in practice         ← Cache efficiency
4. Insertion Sort is O(n) on sorted data     ← Adaptive property
5. Heap Sort is O(1) space, O(n log n) time  ← For memory-constrained systems
6. Merge Sort is stable, guaranteed           ← For linked lists and stability
7. Stability matters when sorting by multiple keys
8. TimSort is the most common real-world sort ← JS, Python, Java, Rust
9. Quick Select finds kth element in O(n) avg ← Partial sorting
10. Dutch National Flag sorts 3 values in O(n) ← Three-way partitioning

Time Complexities:
O(n²):        Bubble, Selection, Insertion (average)
O(n):         Insertion, Bubble (best case — already sorted)
O(n log n):   Merge, Quick (average), Heap
O(n):         Counting, Radix (with constraints)