⚡Flashcard Drill➔
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

  1. The point is to demonstrate that you can implement a real sorting algorithm, not to call sorted.
  2. Merge sort is the safest choice: guaranteed O(n log n), stable, and easy to reason about. The cost is O(n) auxiliary space.
  3. Split the array in half, sort each half recursively, then merge the two sorted halves with two pointers.
  4. 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.
  5. 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() or sorted(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) <= 1 must 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems