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

#include <future>

ostream& operator<<(ostream& out, const vector<int>& vec){
    bool following = false;
    out << "[";
    for(const int it: vec){
        if(following) out << ", ";
        else following = true;
        out << it;
    }
    return out << "]";
}

void heapify(const int begin, vector<int>& nums, const int n, const int i)
{
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && nums[begin + l] > nums[begin + largest])
            largest = l;

        if (r < n && nums[begin + r] > nums[begin + largest])
            largest = r;

        if (largest != i) {
            swap(nums[begin+i], nums[begin+largest]);

            heapify(begin, nums, n, largest);
        }
}

void heapSort(const int begin, const int end, vector<int>& nums)
{
    const int n = end - begin;
    for (int i = (n >> 1) - 1; i >= 0; i--)
        heapify(begin, nums, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(nums[begin], nums[begin + i]);

        heapify(begin, nums, i, 0);
    }
}

#define QUICK_LIMIT 10
#define ASYNC_LIMIT 0

void quickSort2(const int begin, const int end, vector<int>& nums, const int depth){
    if(end - begin <= 1) return;
    if(depth == QUICK_LIMIT) heapSort(begin, end, nums);

    int pivot_limit = begin;

    swap(nums[begin], nums[(begin + end) >> 1]);

    int left = begin;
    int right = end-1;

    while(left < right){
        while(left != right && nums[right] > nums[begin]){
            --right;
        }
        while(left != right && nums[left] <= nums[begin]){
            if(nums[left] == nums[begin] && left != begin){
                swap(nums[++pivot_limit], nums[left]);
            }
            ++left;
        }
        swap(nums[left], nums[right]);
    }
    
    for(int i = 0; i <= pivot_limit - begin; ++i){
        swap(nums[begin+i], nums[left-i]);
    }

    quickSort2(begin, left - pivot_limit + begin, nums, depth + 1);
    quickSort2(left+1, end, nums, depth + 1);
}

void quickSort(const int begin, const int end, vector<int>& nums, const int depth){
    if(end - begin <= 1) return;
    if(depth == QUICK_LIMIT) heapSort(begin, end, nums);

    int pivot_limit = begin;

    swap(nums[begin], nums[(begin + end) >> 1]);

    int left = begin;
    int right = end-1;

    while(left < right){
        while(left != right && nums[right] > nums[begin]){
            --right;
        }
        while(left != right && nums[left] <= nums[begin]){
            if(nums[left] == nums[begin] && left != begin){
                swap(nums[++pivot_limit], nums[left]);
            }
            ++left;
        }
        swap(nums[left], nums[right]);
    }
    
    for(int i = 0; i <= pivot_limit - begin; ++i){
        swap(nums[begin+i], nums[left-i]);
    }

    if(depth == ASYNC_LIMIT){
        auto a1 = std::async(std::launch::async, quickSort2, begin, left - pivot_limit + begin, std::ref(nums), depth + 1);
        auto a2 = std::async(std::launch::async, quickSort2, left+1, end, std::ref(nums), depth + 1);
        
        a1.wait();
        a2.wait();
    }
    else{
        auto a1 = std::async(std::launch::async, quickSort, begin, left - pivot_limit + begin, std::ref(nums), depth + 1);
        auto a2 = std::async(std::launch::async, quickSort, left+1, end, std::ref(nums), depth + 1);
        
        a1.wait();
        a2.wait();
    }

}
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        quickSort(0, nums.size(), nums, 0);
        return std::forward<vector<int>>(nums);
    }
};
56678