Sort an Array

Try It Yourself

Use the editor below to sort the array with merge sort. Separate the recursive splitting step from the helper that combines two sorted halves.

Submit your implementation when it passes the examples. Duplicate, negative, and already sorted values should all work without a built-in sort.

Sort an Array

mediumMerge Sort · Divide and Conquer35 minLC 912

Problem

Given an array of integers, return the values in ascending order.

Implement merge sort instead of using a built-in sorting function.

Example 1:

Input: nums = [5, 2, 3, 1]

Output: [1, 2, 3, 5]

Example 2:

Input: nums = [5, 1, 1, 2, 0, 0]

Output: [0, 0, 1, 1, 2, 5]

Constraints

1 ≤ nums.length ≤ 50,000
-50,000 ≤ nums[i] ≤ 50,000

0 attempts

Solution

Recursively split the array until every piece contains at most one value. Those small pieces are already sorted.

Merge two sorted pieces by repeatedly taking their smaller front value, then append the remainder of the unfinished piece.

function sortArray(nums) {
  function merge(left, right) {
    const result = [];
    let first = 0;
    let second = 0;

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

    return result.concat(left.slice(first), right.slice(second));
  }

  function mergeSort(values) {
    if (values.length <= 1) return values;

    const middle = Math.floor(values.length / 2);
    const left = mergeSort(values.slice(0, middle));
    const right = mergeSort(values.slice(middle));

    return merge(left, right);
  }

  return mergeSort(nums);
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n log n)`	There are logarithmic split levels and each level merges n values.
Auxiliary space	`O(n)`	Merged arrays and recursive slices require linear auxiliary storage.