912. Sort an Array - Explanation

Description

You are 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 functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [10,9,1,1,1,2,3,1]

Output: [1,1,1,1,2,3,9,10]

Example 2:

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

Output: [1,2,3,5,10]

Constraints:

1 <= nums.length <= 50,000.
-50,000 <= nums[i] <= 50,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Quick Sort

Intuition

Quick sort works by selecting a pivot element and partitioning the array so that elements smaller than the pivot go to its left and larger elements go to its right. This implementation uses median-of-three pivot selection (comparing left, middle, and right elements) to avoid worst-case performance on already sorted arrays. After partitioning, we recursively sort the two halves.

Algorithm

Base case: if the subarray has 0 or 1 elements, handle directly with a simple swap if needed.
Select pivot using median-of-three: compare elements at left, middle, and right positions.
Partition the array:
- Move elements smaller than pivot to the left side.
- Move elements larger than pivot to the right side.
- Place the pivot in its final sorted position.
Recursively apply quick sort to the left and right partitions.
Return the sorted array.

class Solution:
    def partition(self, nums: List[int], left: int, right: int) -> int:
        mid = (left + right) >> 1
        nums[mid], nums[left + 1] = nums[left + 1], nums[mid]

        if nums[left] > nums[right]:
            nums[left], nums[right] = nums[right], nums[left]
        if nums[left + 1] > nums[right]:
            nums[left + 1], nums[right] = nums[right], nums[left + 1]
        if nums[left] > nums[left + 1]:
            nums[left], nums[left + 1] = nums[left + 1], nums[left]

        pivot = nums[left + 1]
        i = left + 1
        j = right

        while True:
            while True:
                i += 1
                if not nums[i] < pivot:
                    break
            while True:
                j -= 1
                if not nums[j] > pivot:
                    break
            if i > j:
                break
            nums[i], nums[j] = nums[j], nums[i]

        nums[left + 1], nums[j] = nums[j], nums[left + 1]
        return j

    def quickSort(self, nums: List[int], left: int, right: int) -> None:
        if right <= left + 1:
            if right == left + 1 and nums[right] < nums[left]:
                nums[left], nums[right] = nums[right], nums[left]
            return

        j = self.partition(nums, left, right)
        self.quickSort(nums, left, j - 1)
        self.quickSort(nums, j + 1, right)

    def sortArray(self, nums: List[int]) -> List[int]:
        self.quickSort(nums, 0, len(nums) - 1)
        return nums

Time & Space Complexity

Time complexity: $O(n \log n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(\log n)$ for recursive stack.

2. Merge Sort

Intuition

Merge sort divides the array into two halves, recursively sorts each half, and then merges the sorted halves. The merge step combines two sorted arrays into one by repeatedly picking the smaller element from the front of each array. This divide-and-conquer approach guarantees O(n log n) time regardless of input order.

Algorithm

Base case: if the subarray has one or zero elements, it is already sorted.
Find the middle index and recursively sort the left half (l to mid) and right half (mid + 1 to r).
Merge the two sorted halves:
- Create temporary arrays for left and right portions.
- Compare elements from both arrays and place the smaller one into the result.
- Copy any remaining elements from either array.
Return the sorted array.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge(arr, L, M, R):
            left, right = arr[L:M+1], arr[M+1:R+1]
            i, j, k = L, 0, 0

            while j < len(left) and k < len(right):
                if left[j] <= right[k]:
                    arr[i] = left[j]
                    j += 1
                else:
                    arr[i] = right[k]
                    k += 1
                i += 1

            while j < len(left):
                arr[i] = left[j]
                j += 1
                i += 1

            while k < len(right):
                arr[i] = right[k]
                k += 1
                i += 1

        def mergeSort(arr, l, r):
            if l >= r:
                return
            m = (l + r) // 2
            mergeSort(arr, l, m)
            mergeSort(arr, m + 1, r)
            merge(arr, l, m, r)

        mergeSort(nums, 0, len(nums) - 1)
        return nums

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Heap Sort

Intuition

Heap sort uses a binary heap data structure to sort elements. First, we build a max-heap from the array, which places the largest element at the root. Then we repeatedly extract the maximum (swap it to the end) and restore the heap property. This process naturally sorts the array from smallest to largest.

Algorithm

Build a max-heap by calling heapify on all non-leaf nodes from bottom to top.
The largest element is now at index 0.
Swap the root (maximum) with the last unsorted element.
Reduce the heap size by one and heapify the root to restore the max-heap property.
Repeat steps 3 and 4 until the heap size is 1.
Return the sorted array.

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

    def heapify(self, arr, n, i):
        l = (i << 1) + 1
        r = (i << 1) + 2
        largestNode = i

        if l < n and arr[l] > arr[largestNode]:
            largestNode = l

        if r < n and arr[r] > arr[largestNode]:
            largestNode = r

        if largestNode != i:
            arr[i], arr[largestNode] = arr[largestNode], arr[i]
            self.heapify(arr, n, largestNode)

    def heapSort(self, arr):
        n = len(arr)
        for i in range(n // 2 - 1, -1, -1):
            self.heapify(arr, n, i)

        for i in range(n - 1, 0, -1):
            arr[0], arr[i] = arr[i], arr[0]
            self.heapify(arr, i, 0)

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(\log n)$ for recursive stack.

4. Counting Sort

Intuition

Counting sort works by counting the frequency of each distinct value, then reconstructing the sorted array by outputting each value the appropriate number of times. This is efficient when the range of values (max - min) is not significantly larger than the number of elements. It avoids comparisons entirely.

Algorithm

Find the min and max values in the array.
Create a count map to store the frequency of each value.
Iterate through the array, incrementing the count for each value.
Iterate from min to max value:
- For each value with a positive count, place it into the array the appropriate number of times.
- Decrement the count as values are placed.
Return the sorted array.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def counting_sort():
            count = defaultdict(int)
            minVal, maxVal = min(nums), max(nums)
            for val in nums:
                count[val] += 1

            index = 0
            for val in range(minVal, maxVal + 1):
                while count[val] > 0:
                    nums[index] = val
                    index += 1
                    count[val] -= 1

        counting_sort()
        return nums

Time & Space Complexity

Time complexity: $O(n + k)$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $k$ is the range between the minimum and maximum values in the array.

5. Radix Sort

Intuition

Radix sort processes integers digit by digit, from least significant to most significant. For each digit position, we use counting sort as a stable subroutine. Since counting sort is stable, the relative order from previous digit sorts is preserved. To handle negative numbers, we separate them, sort their absolute values in reverse, and concatenate.

Algorithm

Separate numbers into negatives (converted to positive) and positives.
For each group, apply radix sort:
- Determine the maximum element to know how many digit passes are needed.
- For each digit position (units, tens, hundreds, etc.):
  - Use counting sort based on the current digit.
  - Maintain stability by processing from right to left.
Reverse the sorted negatives and negate them back.
Concatenate negatives and positives to form the final sorted array.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def countSort(arr, n, d):
            count = [0] * 10
            for num in arr:
                count[(num // d) % 10] += 1
            for i in range(1, 10):
                count[i] += count[i - 1]

            res = [0] * n
            for i in range(n - 1, -1, -1):
                idx = (arr[i] // d) % 10
                res[count[idx] - 1] = arr[i]
                count[idx] -= 1

            for i in range(n):
                arr[i] = res[i]

        def radixSort(arr):
            n = len(arr)
            max_element = max(arr)
            d = 1
            while max_element // d > 0:
                countSort(arr, n, d)
                d *= 10

        negatives = [-num for num in nums if num < 0]
        positives = [num for num in nums if num >= 0]

        if negatives:
            radixSort(negatives)
            negatives = [-num for num in reversed(negatives)]

        if positives:
            radixSort(positives)

        return negatives + positives

Time & Space Complexity

Time complexity: $O(d * n)$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $d$ is the number of digits in the maximum element of the array.

6. Shell Sort

Intuition

Shell sort is a generalization of insertion sort that allows exchanges of elements far apart. It starts by sorting elements at a large gap, then progressively reduces the gap. This allows elements to move quickly toward their final positions. When the gap becomes 1, it performs a standard insertion sort on an already nearly-sorted array.

Algorithm

Start with a gap of n / 2.
For each gap value:
- Perform a gapped insertion sort: for each element, compare with elements gap positions behind.
- Shift elements forward by gap until the correct position is found.
- Insert the element.
Reduce the gap by half and repeat until gap is 0.
Return the sorted array.

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def shell_sort(nums, n):
            gap = n // 2
            while gap >= 1:
                for i in range(gap, n):
                    tmp = nums[i]
                    j = i - gap
                    while j >= 0 and nums[j] > tmp:
                        nums[j + gap] = nums[j]
                        j -= gap
                    nums[j + gap] = tmp
                gap //= 2

        n = len(nums)
        if n == 1:
            return nums
        shell_sort(nums, n)
        return nums

Time & Space Complexity

Time complexity: $O(n \log n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(1)$

Common Pitfalls

Using Naive Quick Sort Pivot Selection

Choosing the first or last element as the pivot without any randomization or median selection causes O(n^2) time complexity on sorted or nearly-sorted arrays. Always use randomized pivot selection or median-of-three to avoid worst-case performance on common input patterns.

Forgetting to Handle Negative Numbers in Radix Sort

Radix sort only works directly on non-negative integers. If you apply radix sort to an array containing negative numbers without first separating them, the algorithm produces incorrect results. You must handle negatives separately by converting them to positive, sorting, reversing, and negating back.

Stack Overflow in Recursive Implementations

Deep recursion in merge sort or quick sort can cause stack overflow on very large arrays. For production code, consider iterative implementations or ensure tail-call optimization where available. Some languages have strict stack limits that recursive sorting algorithms can exceed.