DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Sort an Array - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

Analysis for Sorting Algorithm with O(n log n) Time and Minimal Space

The requirement is to implement a sorting algorithm with O(n log n) time complexity while using the smallest possible space, ideally in-place.

Let’s evaluate the standard O(n log n) sorting algorithms:

  • Merge Sort:

    • Time Complexity: O(n log n)
    • Space Complexity: O(n) (due to the need for additional arrays during merging). Not in-place in its standard form.

  • Quick Sort:

    • Time Complexity: O(n log n) on average, O(n²) in worst case.
    • Space Complexity: O(log n) due to recursive stack space. Not strictly in-place since it uses call stack space, but does not use additional arrays.

  • Heap Sort:

    • Time Complexity: O(n log n)
    • Space Complexity: O(1) (in-place sorting).
      Works by transforming the input array into a heap and sorting in-place.

✅ Conclusion:

Among the common O(n log n) sorting algorithms, Heap Sort is the only one that satisfies both conditions:

  • Guaranteed O(n log n) time.
  • Truly in-place sorting with O(1) extra space.

So, Heap Sort is the best choice for this requirement.

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

        heap_size = 0
        n = len(nums)      

        def max_heapify(idx):       # O(log n)
            nonlocal heap_size
            largest = idx
            left, right = 2 * idx + 1, 2 * idx + 2
            
            if left < heap_size and nums[left] > nums[largest]:
                largest = left   
            if right < heap_size and nums[right] > nums[largest]:
                largest = right
            
            if largest != idx:
                nums[largest], nums[idx] = nums[idx], nums[largest]   # swap
                max_heapify(largest)

        def build_heap():           # O(n)
            nonlocal heap_size
            heap_size = n
            for idx in range(len(nums) // 2 - 1, -1 , -1):
                max_heapify(idx)
        
        def heap_sort():            # O(n log n)
            nonlocal heap_size
            build_heap()                        
            for idx in range(n - 1, 0, -1):   # from n-1 down to 1 (leaving index 0, which ends up in correct place)
                nums[0], nums[idx] = nums[idx], nums[0]
                heap_size -= 1
                max_heapify(0)         

        heap_sort() 
        return nums

Complexity Analysis

Here, n is the number of elements in the input array.

  • Time Complexity: O(n log n)
  • Space Complexity: O(1) - inplace.

This implementation is not in-place, unlike the classic in-place heap sort.
It does not satisfy the constraint of minimal space usage, but is provided here for reference.

import heapq

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        heapq.heapify(nums)     # Builds entire min-heap from list (not just "heapifying" one node)
        result = []                
        while nums:
            result.append(heapq.heappop(nums))  # Fetches the minimum element each time
        return result           # Returns a new sorted list (Not in-place)

Complexity Analysis

Here, n is the number of elements in the input array.

  • Time Complexity: O(n log n)
  • Space Complexity: O(n), due to the additional space required by the result array (not in-place).