Merge Sort

Implement merge sort — the classic divide-and-conquer sorting algorithm. You split the array in half, sort each half recursively, then merge the two sorted halves back into one sorted array. The merge step is what does the real work; the recursion is just bookkeeping that hands the merge two pre-sorted inputs to walk through. The result is O(n log n) time in every case — best, average, and worst — and the algorithm is stable (equal items keep their original relative order).

Signature

// Returns a new sorted array. Does not mutate `arr`.
// `compare` defaults to ascending numeric/lexicographic order
// (the same default Array.prototype.sort uses, but actually correct
//  for numbers — see Notes).
function mergeSort<T>(
  arr: T[],
  compare?: (a: T, b: T) => number
): T[];

Examples

mergeSort([38, 27, 43, 3, 9, 82, 10]);
// → [3, 9, 10, 27, 38, 43, 82]

mergeSort([]);          // → []
mergeSort([42]);        // → [42]
mergeSort([5, 1, 4, 2, 8]);
// → [1, 2, 4, 5, 8]

// Custom comparator — descending
mergeSort([3, 1, 4, 1, 5, 9, 2, 6], (a, b) => b - a);
// → [9, 6, 5, 4, 3, 2, 1, 1]

// Custom comparator — by object property
mergeSort(
  [{ age: 30 }, { age: 21 }, { age: 25 }],
  (a, b) => a.age - b.age
);
// → [{ age: 21 }, { age: 25 }, { age: 30 }]

Notes

• Return a new array. Don't mutate the input. Calling mergeSort(x) and then reading x should give back the original order.
• Default comparator must work for numbers. Array.prototype.sort() with no comparator sorts by string representation ([10, 2, 1] becomes [1, 10, 2]). Your default must compare numerically — (a, b) => a < b ? -1 : a > b ? 1 : 0 is the safe form that also works for strings.
• Stability is required. When two elements compare as equal (compare(a, b) === 0), the one that appeared earlier in the input must appear earlier in the output. Tests check this with tagged objects.
• Empty and single-element arrays return as-is — but still as a new array, not the same reference.
• No Array.prototype.sort. That defeats the exercise. Implement the split + merge yourself.
• Don't worry about in-place merging. The standard recursive implementation allocates new arrays at each level; that's fine. Optimizing to O(1) extra space is its own much harder problem.