<p>Given an array of integers <code>nums</code>, sort the array in ascending order and return it.</p>

<p>You must solve the problem <strong>without using any built-in</strong> functions in <code>O(nlog(n))</code> time complexity and with the smallest space complexity possible.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,3,1]
<strong>Output:</strong> [1,2,3,5]
<strong>Explanation:</strong> 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).
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-5 * 10<sup>4</sup> &lt;= nums[i] &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

const static auto initialize = [] {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:

    void swap(int &a, int &b)
    {
        int c=a;
        a=b;
        b=c;
    }

   /*
    int Pivot(int &b, int &e, vector<int> &N)
    {  
         
         int p, i=b+1;

         swap(N[(b+e)/2],N[b]);

         p=N[b];

         for(int v=b+1;v<=e;v++)
         {
             if(N[v]<p) 
             { 
                 swap(N[v],N[i]);
                 i++;
             }
         }

         swap(N[b],N[i-1]);

         return(i-1);
    }
*/

    vector<int> Pivot(int &b, int &e, vector<int> &N)
    {
        int p, i=b, j=e, f=rand()%(e-b); swap(N[f+b],N[b]); p=N[b];

        //cout<<b<<"*****";


        for(int k=b;k<=e && k<=j;k++)
        {
            //cout<<k<<"::";
            //cout<<i<<"::"<<j<<endl;
            if(N[k]<p)
            { 
                //cout<<"hello??? ----";
                 swap(N[i],N[k]);
                 i++;
                 k--;
            }
            else if(N[k]>p)
            {
                 swap(N[j],N[k]);
                 j--;
                 k--;
            }

        }
        vector<int> ret={i,j};
        return(ret);
    }



    void QuickSort(int b, int e, vector<int> &N)
    {
       // cout<<b<<"::"<<e<<endl;
        if(e<=b) return;

        vector<int> P= Pivot(b,e,N);
        
        //cout<<P[0]<<":::"<<P[1]<<endl;
        QuickSort(b,P[0]-1,N);
        QuickSort(P[1]+1,e,N);
    }

    void QuickSort(vector<int> &N)
    {
        QuickSort(0,N.size()-1,N);
    }
    
    vector<int> sortArray(vector<int>& N) {

        //random_shuffle(N.begin(),N.end());
        //N={-4,0,7,4,9,-5,-1,0,4,4,4,4,4-7,-1};
    
        QuickSort(N);

        return(N);
        
    }
};
164326