912. 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 necessarily unique.

 code

class solution{

    public int[] sortArray(int[] arr){

        int n = arr.length;

        for(int i = (n/2) -1  ; i >=0;i--){

                heapify(arr,n,i);

        }

        for(int i = n-1;i>0;i--){

            int temp = arr[i];

                arr[i] = arr[0];

                arr[0] = temp;

                heapify(arr,i,0) ;

        }

    return arr;

    }

    pubic void heapify(int[] arr,int n,int i){

            int larg = i;

            int left = 2*i+1;

            int right = 2*i+2;

            if(left < n && arr[left] > arr[larg]) larg = left;

            if(right < n && arr[right] > arr[larg]) larg = right; 

             if(larg != i){

                    swap(arr[larg],arr[i]);

                    heapify(arr,n,larg);

            }

    }