Sort an Array Using Merge Sort

1. Define the problem

Given an integer array nums, sort it in ascending order without using a built-in sort — implement merge sort directly. Split the array in half recursively until each piece is trivially sorted, then merge pairs of sorted pieces back together with a two pointer walk.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
-5 × 10⁴ ≤ nums_i ≤ 5 × 10⁴

Example

Inputnums = [5, 2, 3, 1]

Output[1, 2, 3, 5]

Explanation Splitting [5, 2, 3, 1] down to single elements and merging the sorted pieces back together produces [1, 2, 3, 5].

2. Visualize the solution

Split down to single elements, then merge back together

Statussplit

Split [5, 2, 3, 1] at mid=2 → [5, 2] and [3, 1].

What happens in this step

nums = [5, 2, 3, 1]
mid = floor(4 / 2) = 2

left  = nums.slice(0, 2) = [5, 2]
right = nums.slice(2)    = [3, 1]

Neither half is trivially sorted yet (each has more than 1 element), so both recurse further before any merging happens.

Step 1 of 6

Steps to visualize

If the array has 0 or 1 elements, it's already sorted — return it as is.
Otherwise split the array at the midpoint into two halves.
Recursively sort each half the same way.
Merge the two sorted halves back together, always taking the smaller front value.
The recursion bottoms out at single elements and builds back up into one fully sorted array.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Split down to single elements, then merge back together

Statussplit

Split [5, 2, 3, 1] at mid=2 → [5, 2] and [3, 1].

What happens in this step

nums = [5, 2, 3, 1]
mid = floor(4 / 2) = 2

left  = nums.slice(0, 2) = [5, 2]
right = nums.slice(2)    = [3, 1]

Neither half is trivially sorted yet (each has more than 1 element), so both recurse further before any merging happens.

Step 1 of 6

4. Solution

Solution

solution.tsTypeScript

function sortArray(nums) {
  if (nums.length <= 1) return nums;

  const mid = Math.floor(nums.length / 2);
  const left = sortArray(nums.slice(0, mid));
  const right = sortArray(nums.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

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

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

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

5. Test cases

Test cases

Input	Expected	Covers
`nums = [5, 2, 3, 1]`	`[1, 2, 3, 5]`	example from the docstring
`nums = []`	`[]`	empty array
`nums = [7]`	`[7]`	smallest valid input, a single element
`nums = [1, 2, 3]`	`[1, 2, 3]`	already sorted, no swaps needed
`nums = [5, 4, 3, 2, 1]`	`[1, 2, 3, 4, 5]`	fully descending input
`nums = [3, 1, 3, 2, 1]`	`[1, 1, 2, 3, 3]`	repeated values
`nums = [-3, 1, -1, 0]`	`[-3, -1, 0, 1]`	mix of negative and non-negative values
`nums = [9, 1, 8, 2, 7, 3, 6]`	`[1, 2, 3, 6, 7, 8, 9]`	odd-length array that splits unevenly

Sort an Array Using Merge Sort