Merge Sort is a highly efficient, comparison-based, stable sorting algorithm. It uses the divide-and-conquer strategy to break an array into smaller sub-arrays, sort them, and merge them back together.

Imagine you have a Gigantic Pile of Socks to sort:

1. It's too big to handle at once.
2. So you split the pile into two halves.
3. You give one half to your friend and keep one half.
4. You both keep splitting until you each have piles of just 1 sock (A single sock is always sorted!).
5. Now, you and your friend merge your sorted piles back together, comparing socks as you go to make sure they stay in order.
6. Eventually, you merge your two big sorted halves into one perfectly sorted pile.

---

Complexity Analysis

• Time: $O(n \log n)$ in all cases (Best, Average, Worst).
• Space: $O(n)$ because we need extra space to store the merged elements.

Key Characteristics

• Stable: It preserves the original order of equal elements.
• Not In-Place: It requires additional memory ($O(n)$ extra space).
• Predictable: Unlike Quicksort, it never degrades to $O(n^2)$.

---

javascript Standard
/**
 * 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);
}

/**
 * Helper: Merge two sorted arrays
 */
function merge(left, right) {
  let result = [];
  let lIndex = 0;
  let rIndex = 0;

  while (lIndex < left.length && rIndex < right.length) {
    if (left[lIndex] < right[rIndex]) {
      result.push(left[lIndex]);
      lIndex++;
    } else {
      result.push(right[rIndex]);
      rIndex++;
    }
  }

  // Concatenate remaining elements
  return result.concat(left.slice(lIndex)).concat(right.slice(rIndex));
}

---

Top Use Cases

• External Sorting: When data is too large to fit in RAM and must be sorted from a disk.
• Linked Lists: Merge Sort is the preferred sorting algorithm for Linked Lists because it doesn't require random access (unlike Quicksort).

Common Questions

• Why is Merge Sort preferred for sorting Linked Lists?
• Is Merge Sort an in-place algorithm?
• Compare Merge Sort vs. Quick Sort. When would you choose one over the other?