<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>

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int>nums_nonNeg;
        vector<int>nums_neg;
        int maxVal_nonNeg, maxVal_neg;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] >= 0)
                nums_nonNeg.push_back(nums[i]);
            else
                nums_neg.push_back(-nums[i]);
        }
        vector<queue<int>>digitArr(10, queue<int>());
        int tens = 1;
        if(nums_nonNeg.size() > 0)
        {
            maxVal_nonNeg = *max_element(nums_nonNeg.begin(), nums_nonNeg.end());
            while(tens <= maxVal_nonNeg)
            {
                for(int i = 0; i < nums_nonNeg.size(); ++i)
                {
                    digitArr[(nums_nonNeg[i]) / tens % 10].push(nums_nonNeg[i]);
                }
                int idx = 0;
                for(int i = 0; i < 10; ++i)
                {
                    while(!digitArr[i].empty())
                    {
                        nums_nonNeg[idx++] = digitArr[i].front();
                        digitArr[i].pop();
                    }
                }
                tens *= 10;
            }
        }  
        if(nums_neg.size() > 0)
        {
            tens = 1;
            maxVal_neg = *max_element(nums_neg.begin(), nums_neg.end());
            while(tens <= maxVal_neg)
            {
                for(int i = 0; i < nums_neg.size(); ++i)
                {
                    digitArr[(nums_neg[i]) / tens % 10].push(nums_neg[i]);
                }
                if(digitArr[0].size() == nums_neg.size())
                    break;
                int idx = 0;
                for(int i = 0; i < 10; ++i)
                {
                    while(!digitArr[i].empty())
                    {
                        nums_neg[idx++] = digitArr[i].front();
                        digitArr[i].pop();
                    }
                }
                tens *= 10;
            }
        }
        int idx = 0;
        for(int i = nums_neg.size()-1; i >= 0; --i)
            nums[idx++] = -nums_neg[i];
        for(int i = 0; i < nums_nonNeg.size(); ++i)
            nums[idx++] = nums_nonNeg[i];
        return nums;
    }
};
87931