Зачем нужен Merge Sort?

Merge Sort — стабильный алгоритм сортировки слиянием со сложностью O(n log n) в худшем, среднем и лучшем случаях. Его используют, когда нужна гарантированная производительность и стабильность (сохранение порядка равных элементов). В JavaScript движок V8 использует Timsort (гибрид сортировки слиянием и вставками) для Array.prototype.sort.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  return merge(
    mergeSort(arr.slice(0, mid)),
    mergeSort(arr.slice(mid))
  );
}
function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }
  return result.concat(left, right);
}

Коротко для собеседования

Merge Sort стабилен и всегда работает за O(n log n), но тратит O(n) дополнительной памяти. Его выбирают, когда важны гарантированное время и сохранение порядка равных элементов.