Sort an Array

Difficulty: Medium

Problem

Given an array of integers nums, sort the array in ascending order and return it. You must solve the problem without using any built-in sort functions in O(n log n) time complexity and with the smallest space complexity possible.

Example

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
Explanation: After sorting the array, the positions change to [1, 2, 3, 5].

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)