<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 final {
private:
    template<class T, class Container = deque<T>>
    class DefaultMerger final {
    private:
        mutable queue<T, Container> buffer{};

    public:
        template<class Iter>
        constexpr void operator()(
            Iter first,
            const Iter middle,
            const Iter last
        ) const noexcept {
            if (middle == last)
                return;

            auto second{middle};
            auto leftNonEmpty{first != middle};
            while (leftNonEmpty || !empty(buffer)) {
                if (leftNonEmpty)
                    buffer.push(move(*first));
                if (empty(buffer) || (second != last && *second < buffer.front())) {
                    *first = move(*second);
                    ++second;
                } else {
                    *first = move(buffer.front());
                    buffer.pop();
                }
                ++first;
                leftNonEmpty = leftNonEmpty && first != middle;
            }
        }
    };

    template<class T>
    class RotateMerger final {
    public:
        template<class Iter>
        constexpr void operator()(
            const Iter first,
            Iter middle,
            const Iter last
        ) const noexcept {
            if (first == middle || middle == last)
                return;

            const auto leftSize{distance(first, middle)},
                rightSize{distance(middle, last)};
            Iter leftIter, rightIter;
            if (leftSize < rightSize) {
                rightIter = next(middle, (rightSize + 1) >> 1);
                leftIter = upper_bound(first, middle, *prev(rightIter));
                middle = prev(rotate(leftIter, middle, rightIter));
            } else {
                leftIter = next(first, (leftSize - 1) >> 1);
                rightIter = lower_bound(middle, last, *leftIter);
                middle = rotate(leftIter, middle, rightIter);
            }
            (*this)(first, leftIter, middle);
            (*this)(next(middle), rightIter, last);
        }
    };

    template<class Iter, class Merger>
    static constexpr void mergeSort(
        const Iter first,
        const Iter last,
        const Merger &merger
    ) noexcept {
        using Difference = iterator_traits<Iter>::difference_type;

        const auto size{distance(first, last)}, half{size >> 1};
        Difference width{1};
        while (width < size) {
            auto n{size};
            auto iter{first};
            while (n != 0) {
                const auto left{min(width, n)}, right{min(width, n - left)};
                const auto middle{next(iter, left)},
                    nextIter{next(middle, right)};
                merger(iter, middle, nextIter);
                n -= left + right;
                iter = nextIter;
            }
            width = width <= half ? width << 1 : size;
        }
    }

public:
    constexpr vector<int> sortArray(vector<int> &nums) const noexcept {
        mergeSort(begin(nums), end(nums), RotateMerger<int>{});
        return move(nums);
    }
};

32371