Sort an Array

Interview Problem Interview Medium Two Pointers Array Divide and Conquer

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.sortArray(nums). Return the values in ascending order using merge sort rather than Python's built-in sorted or list.sort.

Starter code

class Solution:
    def sortArray(self, nums):
        pass

Test cases

mixed

{
  "args": [
    [
      5,
      2,
      3,
      1
    ]
  ]
}

Expected: [1,2,3,5]

Wizard outline

Step 1: Initialize Solution.sortArray
Replace the empty starter with the first real state owned by Solution.sortArray. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Merge Two Values case
Complete the readable core algorithm for one representative Interview case. Recursively sort halves and merge them with two forward pointers.
Step 3: Harden the Mixed boundary
Repair the reviewed boundary and pass the complete submission contract. By induction, recursive calls return sorted halves. The merge always emits the smallest remaining front, so its output is sorted and contains every input value exactly once.

Footguns and prerequisites

After the main merge loop, one half may still contain unconsumed values.
recursion and backtracking
arrays strings two pointers sliding window

Reviewed references

LeetCode 912 — Sort an Array

Practice prerequisites

Merge Two Ordered Runs(opens in a new tab)
Merge Two Ordered Runs isolates the output is sorted and contains exactly the consumed prefixes; the two pointers identify the smallest unconsumed candidates. That focused state discipline is required when implementing sort an array as a complete Interview Problem.

Recommended approach and implementation

Recursively sort two halves, then merge their fronts into a new result and append either remaining suffix.

Why it works: By induction, recursive calls return sorted halves. The merge always emits the smallest remaining front, so its output is sorted and contains every input value exactly once.

class Solution:
    def sortArray(self, nums):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if len(nums) <= 1:
            return nums
        middle = len(nums) // 2
        left = self.sortArray(nums[:middle])
        right = self.sortArray(nums[middle:])
        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