Domain 2MediumMEDIUM

Sort an Array

Implements Merge Sort to achieve O(N log N) time complexity with stable sorting for integer arrays up to length 50,000.

Domain: medium•Updated: 2026-09-03
#Merge Sort#Array/List#O(N log N)#O(N)

Problem Breakdown

The task requires sorting an array of integers nums into ascending order.

  • Inputs: A list of integers (nums).
  • Outputs: The same list sorted in non-decreasing order.
  • Constraints: Array length up to 50,000; values between -50,000 and 50,000.
  • Implicit Constraints: We must handle duplicates correctly (stable sort is often preferred) and negative numbers without special logic beyond standard comparison operators.
  • Edge Cases: While the constraint says 1 <= nums.length, handling an empty list gracefully in code structure demonstrates robustness. Duplicates are common; a stable sorting algorithm preserves their relative order, which can be important if these integers represented indices or objects with hidden state (though not strictly required here).

Intuition

A naive approach would be Bubble Sort or Insertion Sort, both O(N²). With N=50,000, N² is 2.5 billion operations, leading to a Time Limit Exceeded (TLE) on most platforms. We need an algorithm with O(N log N) complexity. The key insight for sorting in interviews when library functions are restricted or to demonstrate understanding of stability/worst-case guarantees is Merge Sort. It provides guaranteed O(N log N) performance regardless of input distribution, unlike QuickSort which can degrade to O(N²). Python’s built-in sort() uses Timsort (a hybrid stable sort), but implementing Merge Sort here proves algorithmic depth.

Approach

  1. Divide: Recursively split the array into two halves until each subarray contains a single element or is empty. A single-element list is inherently sorted.
  2. Conquer/Combine: Define a merge function that takes two sorted arrays and combines them back into one sorted array by comparing elements from both pointers sequentially, appending the smaller value to the result buffer.
  3. Recursion Base Case: Stop recursion when the subarray length is less than or equal to 1.

Complexity Analysis

  • Time Complexity: O(N log N). The divide step halves the array (log N levels), and at each level, we iterate through all elements once (N work) during the merge phase. Total: N * log N.
  • Space Complexity: O(N). We require auxiliary space for the temporary arrays used to store merged results in every recursive call stack frame. In Python specifically, slicing creates copies which contributes linearly per level but total active memory usage remains proportional to input size NN.

Edge Cases Handled

  • Empty/Single Element: The base case len(nums) <= 1 handles these immediately without recursion overhead.
  • Duplicates: The condition left_half[i] <= right_half[j] ensures stability (preserving relative order of equal elements), which is a property often required in production systems handling complex data types.
  • Negative Numbers: Standard integer comparison operators (<=) correctly handle negative values without modification.
  • Large Inputs: The O(N log N) complexity and iterative merging logic ensure it passes within time limits for the 50,000 constraint provided.

Solution

def sort_array(nums):
    # Base case: if array has 0 or 1 element, it is already sorted
    if len(nums) <= 1:
        return nums
    
    mid = len(nums) // 2
    left_half = sort_array(nums[:mid])
    right_half = sort_array(nums[mid:])
    
    # Merge the two sorted halves back together
    merged_list, i, j = [], 0, 0
    
    while i < len(left_half) and j < len(right_half):
        if left_half[i] <= right_half[j]:
            merged_list.append(left_half[i])
            i += 1
        else:
            merged_list.append(right_half[j])
            j += 1
            
    # Append remaining elements from the left half (if any)
    while i < len(left_half):
        merged_list.append(left_half[i])
        i += 1
        
    # Append remaining elements from the right half (if any)
    while j < len(right_half):
        merged_list.append(right_half[j])
        j += 1
        
    return merged_list

# Example usage:
nums = [5,2,3,1]
print(sort_array(nums))