Merge Sort

Sorts an array using merge sort

Problem Overview

The Stable Sorting Powerhouse

Merge Sort is the gold standard for stable, predictable sorting! Using the elegant divide-and-conquer paradigm, it consistently delivers O(n log n) performance regardless of input data distribution.

🧠 The Divide-and-Conquer Strategy:

Divide: Split array into two halves recursively until single elements
Conquer: Sort each half (base case: single elements are already sorted)
Combine: Merge sorted halves back together in sorted order
Stability: Equal elements maintain their relative order (crucial for complex data)
Two Implementation Approaches:
Recursive: Classic top-down approach, elegant and intuitive
Iterative: Bottom-up approach, avoids recursion overhead
Real-World Applications:
Database Systems: Sorting large datasets with predictable performance
External Sorting: Handling datasets larger than available memory
Stable Sort Requirements: When maintaining order of equal elements matters
Parallel Computing: Easy to parallelize due to divide-and-conquer nature
Library Implementations: Foundation for many language standard libraries

💡 Learning Value:

Divide-and-conquer algorithm design paradigm
Recursion tree analysis and complexity calculation
Stable vs unstable sorting trade-offs
Memory usage patterns in sorting algorithms

Concepts

recursiondivide-and-conquer

Complexity Analysis

Time:O(n log n)

Space:O(n)

Performance Notes:

- Time: O(n log n) guaranteed - no worst-case degradation - Space: O(n) for auxiliary arrays during merging

Solutions

mergeSort

Time: O(n log n) | Space: O(n)

export function mergeSort(arr: number[]): number[] {
  if (!Array.isArray(arr) || !arr.every(Number.isFinite)) throw new Error("Input must be an array of finite numbers");
  if (arr.length <= 1) return arr.slice();

  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: number[], right: number[]): number[] {
  const merged: number[] = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) merged.push(left[i++]);
    else merged.push(right[j++]);
  }

  return merged.concat(left.slice(i)).concat(right.slice(j));
}

Examples & Test Cases

#1Unsorted array

Input:

[
  5,
  2,
  8,
  1
]

Output:

[
  1,
  2,
  5,
  8
]

#2Empty array

Input:[]

Output:[]

#3Single element

Input:

[
  1
]

Output:

[
  1
]

#4With duplicates

Input:

[
  3,
  1,
  4,
  1,
  5,
  9,
  2,
  6
]

Output:

[
  1,
  1,
  2,
  3,
  4,
  5,
  6,
  9
]

#5Already sorted

Input:

[
  1,
  2,
  3,
  4
]

Output:

[
  1,
  2,
  3,
  4
]

#6Reverse sorted

Input:

[
  4,
  3,
  2,
  1
]

Output:

[
  1,
  2,
  3,
  4
]