Sort an Array

Problem Description

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(n log(n)) time complexity and with the smallest space complexity possible.

Key Insights

• The task requires sorting an array of integers efficiently.
• We need to achieve a time complexity of O(n log(n)).
• The solution should use minimal additional space.
• Suitable sorting algorithms include Merge Sort, Heap Sort, and variants of Counting Sort for specific conditions (e.g., known range of values).

Space and Time Complexity

Time Complexity: O(n log(n))
Space Complexity: O(1) for in-place algorithms like Heap Sort; O(n) for Merge Sort due to auxiliary space.

Solution

To sort the array efficiently, we can use the Heap Sort algorithm. Heap Sort constructs a binary heap from the input data and then sorts the array in place by repeatedly extracting the maximum element from the heap. This approach ensures that we achieve the desired time complexity of O(n log(n)) while using O(1) space if implemented in place.

1. Build a max heap from the input array.
2. Swap the root of the heap with the last element of the heap.
3. Reduce the size of the heap and heapify the root element.
4. Repeat the process until the heap is empty.

Code Solutions