<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:
    def sortArray(self, nums: List[int]) -> List[int]:
        self.quicsort(nums, 0, len(nums))
        return nums

    def quicsort(self, nums, l, r):
        # print(nums, l, r)
        if r - l <= 1:
            return
        m = r - 1
        self.swap(nums, m, int((l + r) / 2))
        ll = l
        rr = m - 1
        all_same = True
        for i in range(ll, m):
            if nums[i] != nums[m]:
                all_same = False
                break
        if all_same:
            return
        while True:
            while nums[ll] <= nums[m] and ll < m:
                ll += 1
            while rr >= 0 and rr > ll and nums[rr] >= nums[m]:
                rr -= 1
            if rr > ll:
                self.swap(nums, ll, rr)
            else:
                break
        self.swap(nums, m, ll)
        self.quicsort(nums, l, ll)
        self.quicsort(nums, ll + 1, r)


    def swap(self, nums, i, j):
        if i != j:
            tmp = nums[i]
            nums[i] = nums[j]
            nums[j] = tmp

26945