Sort An Array

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 = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104




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

        heapq.heapify(nums)
        return [heapq.heappop(nums) for _ in range(len(nums))]

Random Note

From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict

Python