Sort an Array
Asked at Google
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| MEDIUM | View all Google questions → |
How to Think About It
Bubble sort or insertion sort: simple nested loops — O(n^2) time, does not meet the constraint.
Heap sort: build a max-heap and extract elements one by one — O(n log n) time, O(1) space.
Merge sort: divide array in half, recursively sort each half, then merge — O(n log n) time, O(n) space.
Quick sort: pick a pivot, partition into smaller and larger, recurse — O(n log n) average, O(n^2) worst.
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).
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.