Generated by Codex with GPT-5.4

Difficulty: MEDIUM
Problem: Sort an Array

Problem gist

The task is deliberately simple to state: given an integer array, return the same values in ascending order. The interview signal is not whether someone knows Python’s built-in sort, but whether they can implement a sorting strategy with clear time and space guarantees.

The input may contain negative numbers, duplicates, and values in any order. A correct solution must preserve every occurrence of every number and only change the order.

Deriving the main idea

A direct repeated-swap approach, such as bubble sort or selection sort, is easy to reason about but too slow because it repeatedly scans the array to fix one small piece of order at a time. The better idea is to create sorted regions and combine them efficiently.

Merge sort follows that idea cleanly:

• A one-element region is already sorted.
• Two sorted regions can be merged with two pointers by repeatedly taking the smaller front value.
• If every pass doubles the sorted region size, only about log n passes are needed.
• Each pass moves every number once, so the total time is O(n log n).

The implementation below uses bottom-up merge sort instead of recursive merge sort. That keeps the same asymptotic behavior while avoiding recursion-depth concerns in Python. It uses one reusable buffer, so the extra space is O(n).

There are other valid approaches. If the interviewer allows using the bounded integer range from the constraints, counting sort can be even faster: count how many times each value appears, then write values back in order. If the interviewer prioritizes O(1) extra memory for a comparison sort, heapsort is the usual tradeoff, though it is less stable and more error-prone to implement.

Python solution

from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        """Return nums sorted in ascending order using iterative merge sort."""
        length = len(nums)
        if length < 2:
            return nums

        buffer = nums[:]
        source = nums
        destination = buffer
        run_size = 1

        while run_size < length:
            for left_start in range(0, length, 2 * run_size):
                middle = min(left_start + run_size, length)
                right_end = min(left_start + 2 * run_size, length)
                self._merge_sorted_runs(
                    source,
                    destination,
                    left_start,
                    middle,
                    right_end,
                )

            source, destination = destination, source
            run_size *= 2

        if source is not nums:
            nums[:] = source[:]

        return nums

    def _merge_sorted_runs(
        self,
        source: List[int],
        destination: List[int],
        left_start: int,
        middle: int,
        right_end: int,
    ) -> None:
        left_index = left_start
        right_index = middle
        write_index = left_start

        while left_index < middle and right_index < right_end:
            if source[left_index] <= source[right_index]:
                destination[write_index] = source[left_index]
                left_index += 1
            else:
                destination[write_index] = source[right_index]
                right_index += 1
            write_index += 1

        while left_index < middle:
            destination[write_index] = source[left_index]
            left_index += 1
            write_index += 1

        while right_index < right_end:
            destination[write_index] = source[right_index]
            right_index += 1
            write_index += 1

Interview follow-ups

Could this be done with less extra memory?

Yes. Heapsort gives O(n log n) time with O(1) extra array space. The approach is to first transform the array into a max heap, then repeatedly swap the maximum element at the root with the last unsorted position and restore the heap property over the remaining prefix.

This works because the heap always exposes the largest remaining value in O(1) time after heap construction, and each removal costs O(log n) to sift a new root downward. The tradeoff is practical: heapsort is not stable, has less friendly memory access patterns than merge sort, and is easier to get subtly wrong under interview pressure.

What if the value range is small and known?

Counting sort becomes attractive when the array contains integers within a small bounded range. The solution scans once to count each value, then scans the count array from smallest to largest and writes each value back the number of times it appeared.

This can run in O(n + r) time, where r is the size of the value range, with O(r) extra space. It is excellent when r is close to n or fixed by constraints. It is a poor general-purpose answer when values can be huge, sparse, floating-point, or custom comparable objects.

Why not use quicksort?

Randomized quicksort is a common alternative because it sorts in place on average and usually has strong constant factors. It partitions the array around a pivot, recursively sorts values smaller and larger than the pivot, and gets expected O(n log n) time when pivots are balanced often enough.

The risk is worst-case O(n^2) time when pivot choices are consistently bad. Random pivot selection reduces that risk, and three-way partitioning handles many duplicates better by grouping values less than, equal to, and greater than the pivot. For a platform problem where tests may include adversarial cases, deterministic merge sort is often the safer default.

How should duplicates be handled?

Duplicates need to be preserved exactly, not collapsed. Merge sort handles them naturally because equal values are copied one at a time. Using <= when comparing the left and right runs also makes the merge stable: equal values from the left run keep their relative order before equal values from the right run.

For quicksort, duplicates are a reason to consider three-way partitioning. For counting sort, duplicates are represented directly by their counts.

How would the answer change for a linked list?

A linked list does not support efficient random indexing, so array-style heapsort and quicksort become less natural. Merge sort remains a strong fit because splitting and merging lists only needs pointer manipulation.

The expected approach is to split the list into halves with slow and fast pointers, recursively sort each half, and merge the two sorted lists. It still runs in O(n log n) time. Depending on whether the implementation is recursive or iterative, the extra space is O(log n) from recursion or O(1) beyond the list nodes.

Takeaway

For this problem, bottom-up merge sort is a reliable interview answer: it is deterministic, easy to justify, and avoids Python recursion limits. The important discussion is recognizing when a different constraint changes the best tool: counting sort for small integer ranges, heapsort for constant extra space, and randomized quicksort for average-case in-place performance.