NeetCode #92LC-912MediumArrays & HashingNC 250
← Back to All Problems#92 · #912 · Sort an Array(排序数组)
📌 Problem Statement & Constraints
Given an array of integers
nums, sort it in ascending order and return it, without using any built-in sort function. Constraints: 1 <= nums.length <= 5 * 10^4, -5 * 10^4 <= nums[i] <= 5 * 10^4.💡 Core Algorithmic Approaches
- The point is to demonstrate that you can implement a real sorting algorithm, not to call
sorted. - Merge sort is the safest choice: guaranteed O(n log n), stable, and easy to reason about. The cost is O(n) auxiliary space.
- Split the array in half, sort each half recursively, then merge the two sorted halves with two pointers.
- Quick sort uses O(log n) space and has better cache behaviour, but degrades to O(n^2) on sorted input unless you pick a random or median-of-three pivot.
- Given the value range
[-5e4, 5e4], counting sort is also O(n + V) and very fast -- a nice follow-up answer when the range is bounded.
💻 Benchmark Python3 Implementation
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
# Merge sort: guaranteed O(n log n), stable, O(n) auxiliary space
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = self.sortArray(nums[:mid])
right = self.sortArray(nums[mid:])
return self._merge(left, right)
def _merge(self, a: List[int], b: List[int]) -> List[int]:
res = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # '<=' keeps the sort stable
res.append(a[i]); i += 1
else:
res.append(b[j]); j += 1
res.extend(a[i:])
res.extend(b[j:])
return res
# Counting sort: exploits the bounded value range, O(n + V)
class Solution2:
def sortArray(self, nums: List[int]) -> List[int]:
OFFSET = 50000
cnt = [0] * (100001)
for x in nums:
cnt[x + OFFSET] += 1
res = []
for v, c in enumerate(cnt):
if c:
res.extend([v - OFFSET] * c)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n) for merge sort, in every case. Quick sort averages O(n log n) but degrades to O(n^2) on adversarial input. Counting sort is O(n + V) with V = 100001 here.
💾 Space Complexity
O(n) auxiliary for merge sort (the merged halves plus the recursion's temporary slices). Quick sort would be O(log n). Counting sort is O(V) = O(10^5), which is independent of n.
⚠️ Interview Pitfalls & Follow-ups
- Calling
nums.sort()orsorted(nums): explicitly forbidden; the judge may check for it. - Plain quick sort with
nums[0]as pivot: on already-sorted input the recursion depth becomes n and the time becomes O(n^2). Always randomise or use median-of-three. - Using
<instead of<=in the merge comparison: still correct for a plain sort, but it destroys stability. Worth getting right since stability is a common follow-up. - Recursing without a base case:
len(nums) <= 1must return immediately, otherwise the recursion never terminates. - Assuming the value range is unbounded: counting sort is only valid because the constraints bound
nums[i]to 1e5 values.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.