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

constexpr auto fewElementsThreshold = 100;

template <class Iter, class Cmp>
constexpr Iter partition(Iter begin, const Iter end, const Cmp& cmp) {
    const auto pivotVal = end[-1];
    auto p = begin;
    for (; begin + 1 < end; ++begin) {
        if (cmp(*begin, pivotVal) || !cmp(pivotVal, *begin)) {
            std::iter_swap(p++, begin);
        }
    }
    std::iter_swap(p, std::prev(end));
    return p;
}

template <class Iter, class Cmp>
constexpr void insertionSort(const Iter begin, const Iter end, const Cmp& cmp) {
    for (auto iter = std::next(begin); iter < end; ++iter) {
        for (auto i = iter; begin < i && cmp(*i, i[-1]); --i) {
            std::iter_swap(i, std::prev(i));
        }
    }
}

template <class Iter, class Cmp>
constexpr void mergeSort(Iter begin, const Iter end, const Cmp& cmp) {
    const auto sz = std::distance(end, begin);
    if (sz < fewElementsThreshold) {
        return insertionSort(begin, end, cmp);
    }
    using T = std::iterator_traits<Iter>::value_type;
    std::vector<T> left(begin, begin + sz / 2);
    std::vector<T> right(begin + sz / 2, end);
    mergeSort(left.begin(), left.end(), cmp);
    mergeSort(right.begin(), right.end(), cmp);
    auto leftIt = left.begin();
    auto rightIt = right.begin();
    while (leftIt < left.end() && rightIt < right.end()) {
        if (cmp(*leftIt, *rightIt)) {
            *begin++ = *leftIt++;
        } else {
            *begin++ = *rightIt++;
        }
    }
    while (leftIt < left.end()) {
        *begin++ = *leftIt++;
    }
    while (rightIt < right.end()) {
        *begin++ = *rightIt++;
    }
}

template <class Iter, class Cmp>
constexpr void quickSort(const Iter begin, const Iter end, const Cmp& cmp,
                         const size_t maxDepth) {
    const size_t sz = std::distance(end, begin);
    if (sz < fewElementsThreshold) {
        return insertionSort(begin, end, cmp);
    }
    if (maxDepth == 0) {
        return mergeSort(begin, end, cmp);
    }
    const auto p = ::partition(begin, end, cmp);
    quickSort(begin, p, cmp, maxDepth - 1);
    quickSort(p + 1, end, cmp, maxDepth - 1);
}

template <class Iter, class Cmp>
constexpr void introSort(Iter begin, Iter end, const Cmp& cmp) {
    const size_t sz = std::distance(end, begin);
    const size_t maxDepth = std::ceil(std::log2(sz)) * 2;
    quickSort(begin, end, cmp, maxDepth);
}

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        introSort(nums.begin(), nums.end(), std::less<>{});
        return std::move(nums);
    }
};
35843