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

from random import shuffle, randint
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums)==1:
            return nums
        def quickSort(l, r):
            if l>r:
                return
            lb = l-1
            rb = r+1
            k = l
            x = nums[randint(l, r)]
            while k< rb:
                if nums[k]<x:
                    nums[lb+1], nums[k] = nums[k], nums[lb+1]
                    lb+=1
                    k+=1
                elif nums[k]>x:
                    rb-=1
                    nums[rb], nums[k] = nums[k], nums[rb]
                else:
                    k+=1
            quickSort(l, lb)
            quickSort(rb, r)
        quickSort(0, len(nums)-1)
        return nums

        # def merge(a, b):
        #     l1 = 0
        #     l2 = 0
        #     out = []
        #     while l1< len(a) and l2<len(b):
        #         if a[l1]<=b[l2]:
        #             out.append(a[l1])
        #             l1+=1
                
        #         else:
        #             out.append(b[l2])
        #             l2+=1

        #     while l1<len(a):
        #         out.append(a[l1])
        #         l1+=1
        #     while l2<len(b):
        #         out.append(b[l2])
        #         l2+=1
        #     return out

        # def mergeSort(l, r):
        #     if r==l:
        #         return [nums[l]]
        #     if r-l==1:
        #         if nums[r]<nums[l]:
        #             nums[l], nums[r] = nums[r], nums[l]
        #         return [nums[l], nums[r]]
        #     mid = (l+r)//2
        #     left = mergeSort(l, mid)
        #     right = mergeSort(mid+1, r)
        #     return merge(left, right)
        # return mergeSort(0, len(nums)-1)
        # shuffle(nums)
        # def partition(l, r):
        #     x = nums[l]
        #     left = l
        #     right = r
        #     i = l
        #     while i<= right:
        #         if nums[i]<x:
        #             nums[left], nums[i] = nums[i], nums[left]
        #             i+=1
        #             left+=1
        #         elif nums[i]>x:
        #             nums[right], nums[i] = nums[i], nums[right]
        #             right-=1
        #         else:
        #             i+=1
            
        #     return left, right
        # def mysort(l, r):
        #     if r<=l:
        #         return 
        #     else:
        #         left, right = partition(l, r)
        #         mysort(l, left-1)
        #         mysort(right+1, r)

        # l = 0
        # r = len(nums)-1
        # mysort(l, r)
        # return nums

        # def quick_sort(l, r):
        #     if l >= r:
        #         return
        #     x = nums[randint(l, r)]
        #     i, j, k = l - 1, r + 1, l
        #     while k < j:
        #         if nums[k] < x:
        #             nums[i + 1], nums[k] = nums[k], nums[i + 1]
        #             i, k = i + 1, k + 1
        #         elif nums[k] > x:
        #             j -= 1
        #             nums[j], nums[k] = nums[k], nums[j]
        #         else:
        #             k = k + 1
        #     quick_sort(l, i)
        #     quick_sort(j, r)

        # quick_sort(0, len(nums) - 1)
        # return nums
34085