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
    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
  • Merge two sorted halves by comparing elements one by one
  • 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.

Related problems

Keep practising