Sort an Array

Sorting 50,000 values is easy when the input is friendly. This problem is about keeping the same promise when the input fights back.

Quadratic time means the work can grow with the square of the input size. At n = 50_000, that scale is roughly 2.5 billion operations. Insertion sort reaches it on reverse-sorted data; quicksort with a careless first-or-last pivot can reach it on sorted, reverse-sorted, or all-equal data. Those aren't obscure accidents — they're exactly the shapes a robust sorter must absorb.

Insertion sort — a useful baseline that misses the contract

Keep a sorted region on the left. Take the next value, shift every larger value one place to the right, and insert the value into the gap.

def sort_array(nums: list[int]) -> list[int]:
    for i in range(1, len(nums)):
        value = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > value:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = value
    return nums

This is clean and correct, but on a reverse-sorted array the value handled at step i must cross all i positions already processed.

Time O(n²) in the worst case. Space O(1) — it can take about n(n - 1) / 2 shifts. That fails this problem's required guarantee. Keep it as a baseline, then replace it with one of the guaranteed methods below.

Heap sort — keep the worst case in bounds

A max-heap is an array-shaped tree where every parent is at least as large as its children. Once the array has that shape, its largest value sits at index 0.

Build the heap, swap its largest value into the last open position, shrink the open region, and push the new root downward until the heap rule returns. Repeat until every position is fixed.

def sort_array(nums: list[int]) -> list[int]:
    def sift_down(root: int, end: int) -> None:
        while True:
            child = 2 * root + 1
            if child > end:
                return
 
            if child + 1 <= end and nums[child] < nums[child + 1]:
                child += 1
            if nums[root] >= nums[child]:
                return
 
            nums[root], nums[child] = nums[child], nums[root]
            root = child
 
    n = len(nums)
    for root in range(n // 2 - 1, -1, -1):
        sift_down(root, n - 1)
 
    for end in range(n - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]
        sift_down(0, end - 1)
 
    return nums

Time O(n log n). Space O(1) — building the heap takes O(n), and each of the n extractions repairs at most the heap's O(log n) height. The swaps happen inside the returned array.

Merge sort — combine sorted runs

A run is one contiguous region that is already sorted. Every one-value run starts sorted. Merge adjacent runs of width 1 into width 2, then width 2 into width 4, doubling the width after each full pass.

During a merge, compare the first unused value from each run. Copy the smaller one into a buffer, then finish whichever run still has values left.

def sort_array(nums: list[int]) -> list[int]:
    n = len(nums)
    source = nums[:]
    buffer = [0] * n
    width = 1
 
    while width < n:
        for left in range(0, n, 2 * width):
            middle = min(left + width, n)
            right = min(left + 2 * width, n)
            i, j, write = left, middle, left
 
            while i < middle and j < right:
                if source[i] <= source[j]:
                    buffer[write] = source[i]
                    i += 1
                else:
                    buffer[write] = source[j]
                    j += 1
                write += 1
 
            while i < middle:
                buffer[write] = source[i]
                i += 1
                write += 1
            while j < right:
                buffer[write] = source[j]
                j += 1
                write += 1
 
        source, buffer = buffer, source
        width *= 2
 
    return source

After each pass, every run of the new width is sorted because it was built from two sorted runs. Once the width reaches n, the whole array is one sorted run.

Time O(n log n). Space O(n) — each pass copies n values, there are O(log n) passes, and the reusable buffer holds n values.

Heap sort spends less extra memory; merge sort gives especially direct reasoning and predictable work. Both keep their O(n log n) bound on sorted, reverse-sorted, and all-equal inputs. Randomized quicksort is often fast in practice, but its expected O(n log n) bound averages over random pivot choices; it doesn't remove the quadratic worst case.