Sort an array

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr

            # Find the middle point of the array
            middle = len(arr) // 2

            # Divide the array into two halves
            left_half = arr[:middle]
            right_half = arr[middle:]

            # Recursively sort both halves
            left_half = merge_sort(left_half)
            right_half = merge_sort(right_half)

            # Merge the sorted halves
            return merge(left_half, right_half)
        def merge(left, right):
            result = []
            i = j = 0

            # Traverse through both arrays and append smaller element in result
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1

            # Append the remaining elements of left (if any)
            while i < len(left):
                result.append(left[i])
                i += 1

            # Append the remaining elements of right (if any)
            while j < len(right):
                result.append(right[j])
                j += 1

            return result
        return merge_sort(nums)

Sort an Array

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: 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).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.

Constraints:

1 <= nums.length <= 5 * 10⁴
-5 * 10⁴ <= nums[i] <= 5 * 10⁴