MediumArrayDivide and ConquerSortingHeapMerge SortBucket SortRadix SortCounting SortUpdated Sep 2026

912. Sort an Array

Asked at Google

Difficulty

Medium

Time

O(n log n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an array of integers nums. Return a new array that contains the same values arranged in ascending order (smallest first).

The catch: you may not call any built-in sort function. You have to write the sorting logic yourself, and it must run in O(n log n) time. Values may repeat, so equal numbers just sit next to each other.

The intended solution is merge sort: split the array into two halves, sort each half the same way, then merge the two sorted halves into one sorted array by repeatedly taking the smaller front element.

Sort the values in place order

nums52310123Input array in its original, unsorted order.result12350123After sorting, 1 is first and 5 is last.
We must rearrange [5,2,3,1] so the values read from smallest to largest.

Constraints

  • ●1 <= nums.length <= 5 * 10^4
  • ●-5 * 10^4 <= nums[i] <= 5 * 10^4

Examples

Example 1
Inputnums = [5,2,3,1]
Output[1,2,3,5]
WhySorting puts the smallest value 1 first and the largest value 5 last. The middle values 2 and 3 keep their relative order because 2 < 3.
Example 2
Inputnums = [5,1,1,2,0,0]
Output[0,0,1,1,2,5]
WhyThe array has duplicate values, and duplicates are kept. Both 0s come first, then both 1s, then 2, then 5.

Asked At

1 companies
CompanyDifficulty
GoogleMediumView all Google questions →

How to Think About It

1

Bubble sort or insertion sort: simple nested loops — O(n^2) time, does not meet the constraint.

2

Heap sort: build a max-heap and extract elements one by one — O(n log n) time, O(1) space.

3

Merge sort: divide array in half, recursively sort each half, then merge — O(n log n) time, O(n) space.

4

Quick sort: pick a pivot, partition into smaller and larger, recurse — O(n log n) average, O(n^2) worst.

5

Counting or radix sort: non-comparison sorts that work when value range is bounded — O(n) time, O(n) space.

Optimal Approach

Use merge sort, a divide-and-conquer algorithm. Recursively split the array into halves until single elements remain. Then merge two sorted halves by comparing elements from each half and placing the smaller one first. The merge step takes O(n) time and the recursion depth is O(log n), giving O(n log n) total time. This approach guarantees O(n log n) regardless of input distribution, unlike quick sort which can degrade to O(n^2).

Merge sort: split, sort, merge

splitleftright52310123Step 1 — cut the array into two halves.halves sortedsorted leftsorted right25130123Step 2 — each half is sorted on its own: [2,5] and[1,3].merged12350123Step 3 — merge by comparing fronts: 1<2, then 2<3,then 3<5.T(n) = 2·T(n/2) + O(n)= O(n log n)
Split until single elements, then merge sorted halves by always taking the smaller front value.
ComplexityTime O(n log n)Space O(n)The array is halved log n times and each level does O(n) work to merge, while the temporary merged arrays need O(n) extra space.

What Trips People Up in Real Interviews

1

Ask whether the input contains negative numbers — this eliminates radix/bucket sort without adjustment.

2

Clarify space constraints: O(1) space rules out merge sort, favors in-place heap sort or quick sort.

3

Explain the trade-offs between merge sort (stable, guaranteed O(n log n)) and quick sort (in-place, average O(n log n)).

4

Mention counting sort if the value range is small — it beats comparison-based sorts at O(n).

5

Walk through the merge step of merge sort before coding to show you understand the core logic.

Solution Code

O(n log n) time
def sort_array(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = sort_array(nums[:mid])
    right = sort_array(nums[mid:])
    return merge(left, right)

def 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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Sort an Array 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. The solution should demonstrate a comparison-based or non-comparison-based sorting algorithm.

How do you solve Sort an Array?

The optimal approach runs in O(n log n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Sort an Array?

Sort an Array is asked at Google. It is a medium difficulty problem.

What are common mistakes on Sort an Array?
  • Ask whether the input contains negative numbers — this eliminates radix/bucket sort without adjustment.
  • Clarify space constraints: O(1) space rules out merge sort, favors in-place heap sort or quick sort.
  • Explain the trade-offs between merge sort (stable, guaranteed O(n log n)) and quick sort (in-place, average O(n log n)).
  • Mention counting sort if the value range is small — it beats comparison-based sorts at O(n).
  • Walk through the merge step of merge sort before coding to show you understand the core logic.