[Medium] 912. Sort an Array

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem in O(n log n) time complexity and with the smallest possible space complexity.

Examples

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints

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

Solution 1: Merge Sort

Time Complexity: O(n log n)
Space Complexity: O(n)

Merge sort is a divide-and-conquer algorithm that divides the array into two halves, sorts them recursively, and then merges the sorted halves.

class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        cache = [0] * len(nums)
        self.mergeSort(nums, 0, len(nums) - 1, cache)
        return nums

    def mergeSort(self, arr: list[int], left: int, right: int, cache: list[int]) -> None:
        if left >= right:
            return

        mid = (left + right) // 2

        self.mergeSort(arr, left, mid, cache)
        self.mergeSort(arr, mid + 1, right, cache)
        self.merge(arr, left, mid, right, cache)

    def merge(self, arr: list[int], left: int, mid: int, right: int, cache: list[int]) -> None:
        # copy to cache
        for i in range(left, right + 1):
            cache[i] = arr[i]

        i = left
        j = mid + 1
        k = left

        # merge back
        while i <= mid and j <= right:
            if cache[i] <= cache[j]:
                arr[k] = cache[i]
                i += 1
            else:
                arr[k] = cache[j]
                j += 1
            k += 1

        # remaining left side
        while i <= mid:
            arr[k] = cache[i]
            i += 1
            k += 1

        # remaining right side
        while j <= right:
            arr[k] = cache[j]
            j += 1
            k += 1

How Merge Sort Works:

  1. Divide: Split the array into two halves
  2. Conquer: Recursively sort both halves
  3. Combine: Merge the sorted halves back together

The merge operation compares elements from both halves and places them in the correct order.

Solution 2: Heap Sort

Time Complexity: O(n log n)
Space Complexity: O(1)

Heap sort uses a max-heap to sort the array in-place.

class Solution:
    def heapify(self, arr: list[int], n: int, i: int) -> None:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        # Find largest among root and children
        if left < n and arr[left] > arr[largest]:
            largest = left

        if right < n and arr[right] > arr[largest]:
            largest = right

        # If root is not largest, swap and continue heapifying
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            self.heapify(arr, n, largest)

    def heapSort(self, arr: list[int]) -> None:
        n = len(arr)

        # Build max heap
        for i in range(n // 2 - 1, -1, -1):
            self.heapify(arr, n, i)

        # Extract elements one by one
        for i in range(n - 1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]
            self.heapify(arr, i, 0)

    def sortArray(self, nums: list[int]) -> list[int]:
        self.heapSort(nums)
        return nums

How Heap Sort Works:

  1. Build Max Heap: Convert array to max-heap
  2. Extract Maximum: Repeatedly extract the maximum element and place it at the end
  3. Heapify: Maintain heap property after each extraction

Solution 3: Counting Sort

Time Complexity: O(n + k) where k is the range of input
Space Complexity: O(k)

Counting sort works well when the range of numbers is small.

class Solution:
    def countSort(self, arr: list[int]) -> None:
        from collections import defaultdict

        counts = defaultdict(int)

        # Step 1: count frequencies
        for val in arr:
            counts[val] += 1

        minVal = min(arr)
        maxVal = max(arr)

        # Step 2: rebuild array
        idx = 0
        for val in range(minVal, maxVal + 1):
            while counts[val] > 0:
                arr[idx] = val
                idx += 1
                counts[val] -= 1

    def sortArray(self, nums: list[int]) -> list[int]:
        self.countSort(nums)
        return nums

How Counting Sort Works:

  1. Count: Count frequency of each element
  2. Reconstruct: Place elements back in sorted order based on their counts

Algorithm Comparison

Algorithm Time Complexity Space Complexity Stability In-Place
Merge Sort O(n log n) O(n) Stable No
Heap Sort O(n log n) O(1) Unstable Yes
Counting Sort O(n + k) O(k) Stable No

When to Use Each Algorithm

  • Merge Sort: When you need a stable sort and have O(n) extra space
  • Heap Sort: When you need in-place sorting and don’t care about stability
  • Counting Sort: When the range of numbers is small compared to array size

Key Insights

  1. Merge Sort guarantees O(n log n) time complexity and is stable
  2. Heap Sort is in-place but not stable
  3. Counting Sort can be very fast when the range is small
  4. All three solutions meet the O(n log n) requirement for this problem