Sort an Array

Difficulty: Medium

Problem

Reorder the integer array nums so its values go from smallest to largest, and return it. Built-in sort functions are not allowed; aim for O(n log n) running time while using as little extra memory as you can.

Example

Input: nums = [9, 4, 7, 4, 1]
Output: [1, 4, 4, 7, 9]
Explanation: Arranged from smallest to largest, the values become [1, 4, 4, 7, 9]; the repeated 4 stays twice.

Brute-force approach

Use a simple O(n²) sorting algorithm like Selection Sort or Insertion Sort.

Steps

  1. For each position i, find the minimum element in the remaining array
  2. Swap it with the element at position i
  3. Repeat for all positions

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • O(n²) is too slow for large arrays
  • Doesn't meet the O(n log n) requirement

Optimal approach

Key insight: Splitting into halves gives O(log n) levels, and merging at each level takes O(n) work → O(n log n) total.

Use Merge Sort: recursively divide the array in half, then merge the sorted halves.

Steps

  1. Base case: array of size ≤ 1 is already sorted
  2. Split array into two halves at mid
  3. Recursively sort left half and right half
  4. Merge two sorted halves into one sorted array

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

Pseudocode

function sortArray(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2    // whole-number division: a float breaks the slicing
    left = sortArray(nums[:mid])
    right = sortArray(nums[mid:])
    return merge(left, right)

function merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Hints

  • Divide the array in half recursively until each sub-array has 1 element (a list of one card is already sorted)
  • Merge two sorted halves by comparing the two front elements one by one: the smaller front is the smallest card still waiting, so it goes next
  • This is the classic Merge Sort algorithm

Check your understanding of Sort an Array

Why can't we use a simple O(n²) sorting algorithm here?

The problem requires O(n log n) time complexity. The problem explicitly requires O(n log n) time complexity. Algorithms like bubble sort or insertion sort are O(n²) and would be too slow for large inputs.

What is the base case for merge sort?

When the array has 1 or fewer elements. An array with 0 or 1 elements is already sorted by definition. This is our base case to stop recursion.

Why must both halves already be sorted before we merge them?

The merge only looks at the two front elements, and the front of a sorted half is its smallest, so nothing behind it can be smaller. Taking the smaller of the two fronts is safe only when each half is sorted: every element behind a front is at least as big as it. With unsorted halves a smaller card could hide behind a front. On a tie we take the left one, so a merge never swaps two equal cards and the sort is stable.

Related problems

Keep practising