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

&nbsp;
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]

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 5 * 104
	-5 * 104 &lt;= nums[i] &lt;= 5 * 104


import heapq
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        
        h = {}
        for i in nums:
            if i in h:
                h[i]+=1
            else:
                h[i]=1
        
        heap = []
        for i in h:
            heap.append([i,h[i]])
        
        heapq.heapify(heap)
        ans = []
        
        while heap:
            x = heapq.heappop(heap)
            ans.append(x[0])
            if x[1]>1:
                heapq.heappush(heap,[x[0],x[1]-1])
                
        return ans
class Solution {

        public void downHeapify(int[] nums, int startIndex, int lastIndex){

        int parentIndex = startIndex;
        int leftChildIndex = 2*parentIndex + 1;
        int rightChildIndex = 2*parentIndex + 2;

        while(leftChildIndex <= lastIndex){
            int maxIndex = parentIndex;
            if(nums[leftChildIndex] > nums[maxIndex]){
                maxIndex = leftChildIndex;
            }
            if(rightChildIndex <= lastIndex && nums[rightChildIndex] > nums[maxIndex]){
                maxIndex = rightChildIndex;
            }
            if(maxIndex == parentIndex){
                return;
            }
            int temp = nums[maxIndex];
            nums[maxIndex] = nums[parentIndex];
            nums[parentIndex] = temp;
            parentIndex = maxIndex;
            leftChildIndex = 2*parentIndex + 1;
            rightChildIndex = 2*parentIndex + 2;
        }
        return;
    }

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        //building a heap - O(n) time
        for(int i=(len/2)-1;i>=0;i--){
            downHeapify(nums,i,len-1);
        }
        //sorting element - nlogn(n) time
        for(int i=len -1 ;i>0;i--){
             int temp = nums[i];
             nums[i] = nums[0];
             nums[0] = temp;
             downHeapify(nums,0,i-1);
        }
        return nums;

    }
}
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>>pq;
        for(auto it : nums)
        {
            pq.push(it);
        }
        vector<int>ans;
        while(!pq.empty())
        {
            ans.push_back(pq.top());
            pq.pop();
        }

        return ans;
    }
};
var sortArray = function(nums) {
    return quickSort(nums, 0, nums.length - 1);
};

const quickSort = (arr, start, end) => {
    // base case
    if (start >= end) return arr;

    // return pivot index to divide array into 2 sub-arrays.
    const pivotIdx = partition(arr, start, end);
    // sort sub-array to the left and right of pivot index.
    quickSort(arr, start, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, end);

    return arr;
}

const partition = (arr, start, end) => {
    // select a random pivot index, and swap pivot value with end value.
    const pivotIdx = Math.floor(Math.random() * (end - start + 1)) + start;
    [arr[pivotIdx], arr[end]] = [arr[end], arr[pivotIdx]];

    const pivotVal = arr[end];
    // loop from start to before end index (because pivot is stored at end index).
    for (let i = start; i < end; i++) {
        if (arr[i] < pivotVal) {
            // swap smaller-than-pivot value (at i) with the value at the start index.
            // This ensures all values to the left of start index will be less than pivot.
            [arr[i], arr[start]] = [arr[start], arr[i]];
            start++;
        }
    }

    // swap pivot (which was stored at end index) with value at start index.
    // This puts the pivot in its correct place.
    [arr[start], arr[end]] = [arr[end], arr[start]];
    return start;
}

/*
Note: Instead of always picking a fixed index as the pivot (ie. start or end index),
The pivot was randomly selected to mitigate the odds of achieving worst case TC and SC.
TC:
Best and avg case: O(nlogn)
worst case: O(n^2)

SC:
Since algo done in-place, space comes from recursive call stack.
best and avg case: O(logn)
worst case: O(n)
*/
Sort an Array