<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 TreeNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        self.height = 0

class SortedDict:
    def __init__(self):
        self.root = None
        self.dict = {}

    def __inorder(self, node):
        if node is None:
            yield None

        if node.left:
            yield from self.__inorder(node.left)
        yield node.key
        if node.right:
            yield from self.__inorder(node.right)

    def __iter__(self):
        return self.__inorder(self.root)
    
    def get(self, key, alternative=None):
        if key in self.dict:
            return self.dict[key].value
        else:
            return alternative

    def __getitem__(self, key):
        if key in self.dict:
            return self.dict[key].value

    def __setitem__(self, key, value):
        if key in self.dict:
            self.dict[key].value = value
        else:
            node = TreeNode(key, value)
            self.dict[key] = node
            self.root = self.__insert(self.root, node)

    def __diff(self, node):
        return self.__get_height(node.left) - self.__get_height(node.right)

    def __rotate_left(self, node):
        root = node.right
        node.right = root.left
        root.left = node

        node.height = self.__get_height(node)
        root.height = self.__get_height(root)

        return root

    def __rotate_right(self, node):
        root = node.left
        node.left = root.right
        root.right = node

        node.height = self.__get_height(node)
        root.height = self.__get_height(root)

        return root

    def __balance(self, node):
        if node is None:
            return node

        balance = self.__diff(node)
        if balance > 1:
            if node.left and self.__diff(node.left) < 0:
                node.left = self.__rotate_left(node.left)
            node = self.__rotate_right(node)
        elif balance < -1:
            if node.right and self.__diff(node.right) > 0:
                node.right = self.__rotate_right(node.right)
            node = self.__rotate_left(node)
        
        return node

    def __get_height(self, node):
        if node is None:
            return -1

        left = node.left.height if node.left else -1
        right = node.right.height if node.right else -1
        return 1 + max(left, right)

    def __insert(self, head, node):
        if head is None:
            return node

        if head.key > node.key:
            head.left = self.__insert(head.left, node)
        elif head.key < node.key:
            head.right = self.__insert(head.right, node)
        
        head.height = self.__get_height(head)
        return self.__balance(head)

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        count_table = SortedDict()
        for num in nums:
            count_table[num] = count_table.get(num, 0) + 1

        i = 0
        for num in count_table:
            for _ in range(count_table[num]):
                nums[i] = num
                i += 1
        
        return nums
        


33035