# your code goes here
class Solution:
    def sortArray(self, nums):
        if len(nums) <= 1:
            return nums
 
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
 
        return self.merge(left, right)
 
    def merge(self, left, right):
        merged = []
        i = j = 0
 
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
 
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged
 

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCmNsYXNzIFNvbHV0aW9uOgogICAgZGVmIHNvcnRBcnJheShzZWxmLCBudW1zKToKICAgICAgICBpZiBsZW4obnVtcykgPD0gMToKICAgICAgICAgICAgcmV0dXJuIG51bXMKCiAgICAgICAgbWlkID0gbGVuKG51bXMpIC8vIDIKICAgICAgICBsZWZ0ID0gc2VsZi5zb3J0QXJyYXkobnVtc1s6bWlkXSkKICAgICAgICByaWdodCA9IHNlbGYuc29ydEFycmF5KG51bXNbbWlkOl0pCgogICAgICAgIHJldHVybiBzZWxmLm1lcmdlKGxlZnQsIHJpZ2h0KQoKICAgIGRlZiBtZXJnZShzZWxmLCBsZWZ0LCByaWdodCk6CiAgICAgICAgbWVyZ2VkID0gW10KICAgICAgICBpID0gaiA9IDAKCiAgICAgICAgd2hpbGUgaSA8IGxlbihsZWZ0KSBhbmQgaiA8IGxlbihyaWdodCk6CiAgICAgICAgICAgIGlmIGxlZnRbaV0gPD0gcmlnaHRbal06CiAgICAgICAgICAgICAgICBtZXJnZWQuYXBwZW5kKGxlZnRbaV0pCiAgICAgICAgICAgICAgICBpICs9IDEKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIG1lcmdlZC5hcHBlbmQocmlnaHRbal0pCiAgICAgICAgICAgICAgICBqICs9IDEKCiAgICAgICAgbWVyZ2VkLmV4dGVuZChsZWZ0W2k6XSkKICAgICAgICBtZXJnZWQuZXh0ZW5kKHJpZ2h0W2o6XSkKICAgICAgICByZXR1cm4gbWVyZ2VkCg==