⚙️ JavaScript Sorting

Index: Sorting Index | Parent: JS Array Index

---

1. Array.sort() Quirks

⚠ Critical JS Gotcha: Without a compare function, .sort() converts elements to strings and sorts them lexicographically!

// ❌ WRONG — sorts as strings
[10, 9, 2, 100, 21].sort();
// [10, 100, 2, 21, 9]  — "10" < "100" < "2" < "21" < "9"

// ✅ CORRECT — numeric sort
[10, 9, 2, 100, 21].sort((a, b) => a - b);
// [2, 9, 10, 21, 100]

// ✅ Descending
[10, 9, 2, 100, 21].sort((a, b) => b - a);
// [100, 21, 10, 9, 2]

How the comparator works:

(a, b) => a - b

  Result < 0  →  a comes BEFORE b
  Result = 0  →  order unchanged
  Result > 0  →  b comes BEFORE a

---

2. Custom Comparators

// ── Numbers ──────────────────────────────────────
const nums = [3, 1, 4, 1, 5, 9, 2, 6];
nums.sort((a, b) => a - b);  // ascending
nums.sort((a, b) => b - a);  // descending

// ── Strings (case-insensitive) ───────────────────
['Banana','apple','Cherry'].sort((a, b) =>
  a.toLowerCase().localeCompare(b.toLowerCase())
);
// ['apple','Banana','Cherry']

// ── Objects — single key ─────────────────────────
const students = [
  {name:'Carol', grade:88},
  {name:'Alice', grade:95},
  {name:'Bob',   grade:88},
];
students.sort((a, b) => b.grade - a.grade);
// Alice(95), Carol(88), Bob(88)

// ── Objects — multi-key (grade desc, name asc) ───
students.sort((a, b) => {
  if (b.grade !== a.grade) return b.grade - a.grade;
  return a.name.localeCompare(b.name);
});
// Alice(95), Bob(88), Carol(88)

// ── Sort by string length ─────────────────────────
['banana','fig','apple','kiwi'].sort((a,b) => a.length - b.length);
// ['fig','kiwi','apple','banana']

// ── Boolean sort (true first) ─────────────────────
[false, true, false, true].sort((a, b) => b - a);
// [true, true, false, false]

// ── Stable sort guarantee ─────────────────────────
// V8 (Node/Chrome) uses TimSort which is stable since Node 11 / Chrome 70

---

3. Sorting Algorithms

Bubble Sort — O(n²)

function bubbleSort(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]]; // swap
        swapped = true;
      }
    }
    if (!swapped) break; // already sorted
  }
  return arr;
}
// Time: O(n²) avg, O(n) best | Space: O(1)

Selection Sort — O(n²)

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}
// Time: O(n²) always | Space: O(1) | Not stable

Insertion Sort — O(n²)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}
// Time: O(n²) avg, O(n) best (nearly sorted) | Space: O(1) | Stable
// ✅ Best for small or nearly-sorted arrays

Merge Sort — O(n log n)

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 result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else                      result.push(right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Time: O(n log n) always | Space: O(n) | Stable
// ✅ Best for linked lists, external sorting, stable sort needed

Quick Sort — O(n log n) avg

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i+1], arr[high]] = [arr[high], arr[i+1]];
  return i + 1;
}

// Time: O(n log n) avg, O(n²) worst | Space: O(log n) | Not stable
// ✅ Best general-purpose, in-place

Counting Sort — O(n + k)

function countingSort(arr) {
  if (!arr.length) return arr;
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const count = new Array(max - min + 1).fill(0);

  for (const num of arr) count[num - min]++;

  const result = [];
  for (let i = 0; i < count.length; i++) {
    for (let j = 0; j < count[i]; j++) {
      result.push(i + min);
    }
  }
  return result;
}

// Time: O(n + k) k=range | Space: O(k)
// ✅ Best when range (k) is small (e.g. ages 0-100)

---

4. Algorithm Comparison

In interviews: Use arr.sort((a,b) => a-b) unless asked to implement a specific algorithm.

---

5. Interview Questions

---

Q1. Sort Array of 0s, 1s, 2s — Dutch National Flag [M][FB]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Only 3 distinct values + single pass + O(1) space = Dutch National Flag (3-way partition).

Step 2 — Brute force:

Count 0s, 1s, 2s then overwrite → O(n) but 2 passes. Single pass is better.

Step 3 — Dutch National Flag insight:

Maintain 3 regions: [0..low-1]=0s, [low..mid-1]=1s, [high+1..n-1]=2s. The region [mid..high] is unexplored.

Step 4 — Algorithm:

- nums[mid]===0: swap with nums[low], low++, mid++ (0 lands in left region)

- nums[mid]===1: mid++ (1 is already in correct region)

- nums[mid]===2: swap with nums[high], high-- (2 lands in right region; don't advance mid)

Step 5 — Edge cases:

- All same value: pointers pass without swaps

- Already sorted: mid scans through rapidly

Way of Thinking: 3 pointers: low, mid, high. Elements < low are 0s, low..mid-1 are 1s, high+1..end are 2s. Single pass O(n).

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++; mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else { // nums[mid] === 2
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // don't increment mid — swapped element needs checking
    }
  }
  return nums;
}

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

---

Q2. Find Kth Largest Element — Quick Select [M][FB]

---

🧠 How to Approach This

Step 1 — Simple approach:

Sort descending, return index k-1 → O(n log n). Valid in most interviews, mention it first.

Step 2 — Optimal: Quick Select O(n) average:

Partial QuickSort. After partitioning, the pivot is in its final sorted position. Only recurse into the half containing the k-th element.

Step 3 — Key insight:

K-th largest = (n-k)-th smallest (0-indexed). After partition, if pivot index = target: done. If pivot < target: recurse right. If pivot > target: recurse left.

Step 4 — Algorithm:

1. target = n - k

2. partition(arr, low, high) → returns pivot's sorted position

3. Compare pivot position with target, recurse on one side only

Step 5 — Edge cases:

- k=1: find max — pivot always ends up at target position quickly

- Random pivot for guaranteed average O(n)

Way of Thinking: Quick Select is like Quick Sort but only recurse on the side containing the kth element. Average O(n), not O(n log n).

function findKthLargest(nums, k) {
  // kth largest = (n-k)th smallest
  return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

function quickSelect(arr, low, high, k) {
  if (low === high) return arr[low];

  const pivot = partition(arr, low, high);
  if (pivot === k)       return arr[pivot];
  else if (pivot < k)    return quickSelect(arr, pivot + 1, high, k);
  else                   return quickSelect(arr, low, pivot - 1, k);
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i+1], arr[high]] = [arr[high], arr[i+1]];
  return i + 1;
}

// Using sort (simpler but O(n log n))
const kthLargestSimple = (nums, k) =>
  nums.sort((a,b) => b-a)[k-1];

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

---

Q3. Count Inversions in Array [H]

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Count pairs (i,j) where iarr[j] = Modified Merge Sort (count while sorting).

Step 2 — Brute force:

Two nested loops checking every pair → O(n²). Need O(n log n).

Step 3 — Key insight:

During the merge step, if left[i] > right[j], then ALL remaining elements in left[] are also > right[j] (because left is sorted). So inversions += (left.length - i). Count inversions as a side effect of sorting.

Step 4 — Algorithm:

1. Divide array in halves, recursively sort + count each half

2. During merge: when right[j] < left[i], add (left.length - i) inversions

3. Total = leftInversions + rightInversions + mergeInversions

Step 5 — Edge cases:

- Already sorted: 0 inversions

- Reverse sorted [n, n-1, ..., 1]: n*(n-1)/2 inversions (maximum)

Way of Thinking: Modify Merge Sort — while merging, if left[i] > right[j], all remaining left elements also > right[j], so add (mid - i) to count.

function countInversions(arr) {
  let count = 0;

  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 mergeCount(left, right);
  }

  function mergeCount(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++]);
      } else {
        count += left.length - i; // all left[i..] > right[j]
        result.push(right[j++]);
      }
    }
    return result.concat(left.slice(i)).concat(right.slice(j));
  }

  mergeSort(arr);
  return count;
}

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