0912.Sort an Array

Link: 912. Sort an Array

Question

Restate the problem

We need to sort an integer array in ascending order.

Method

Approach - Merge Sort

Merge sort uses divide and conquer:

1. Divide the array into two halves until each subarray has length 0 or 1 (already sorted).
2. Conquer (merge): merge two sorted halves using two pointers:
   • Compare the front elements of both halves
   • Append the smaller one to the result
   • Move that pointer forward
3. Return the merged sorted array.

Complexity

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Edge Case

• if not array

Code

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
 
        def merge(left_arr, right_arr):
            res = []
            left = right = 0
            while left < len(left_arr) and right < len(right_arr):
                if left_arr[left] <= right_arr[right]:
                    res.append(left_arr[left])
                    left += 1
                else:
                    res.append(right_arr[right])
                    right += 1
            
            res.extend(left_arr[left:])
            res.extend(right_arr[right:])
 
            return res
 
        def mergesort(nums):
            if len(nums) <= 1:
                return nums
            
            mid = len(nums) // 2
            left_arr = mergesort(nums[:mid])
            right_arr = mergesort(nums[mid:])
 
            return merge(left_arr, right_arr)
        
        return mergesort(nums)

---

History

Jan-17-2026 Solved w bug, merge condition wrong