Sort an Array

MEDIUM✓ CHIP-TIMEDLC #912 — FULL STATEMENT ↗

The drill: Sort an integer array into ascending order using an algorithm you build yourself rather than a library call — the array is the whole exercise.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives in no particular order, and the job is to rearrange it into ascending order — but the sorting logic has to be built by hand rather than delegated to a library call.

Every value from the input must appear in the output the same number of times it started with; nothing is added, dropped, or invented, only reordered.

Negative numbers, zeros, and duplicates all pass through the same rules as any other value, settling wherever ascending order places them.

EX 01

nums = [5, 2, 3, 1]

→ [1, 2, 3, 5]

EX 02

nums = [1]

→ [1]

SINGLE ELEMENT

EX 03

nums = [5, 4, 3, 2, 1]

→ [1, 2, 3, 4, 5]

REVERSE SORTED, WORST CASE FOR INSERTION SORT

arrays can run up to tens of thousands of elements
values may be negative, zero, or positive, duplicates included
a library sort call is off-limits — the algorithm has to be self-built
the output must be fully ascending, ties in any relative order

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A library sort would solve this in one line, but the exercise is proving you can build the guarantee yourself. What classic method builds a sorted result one comparison at a time?

HINT 2 THE STRUCTURE

Insertion sort is honest and correct but pays quadratically, because a bad ordering can force every new element to slide across everything already placed. Divide and conquer sidesteps that by never comparing across a huge span at once.

HINT 3 ONE STEP FROM THE ANSWER

Split the array in half recursively down to single elements, then merge sorted halves back together two at a time — merging two sorted runs is linear, and there are only log n levels of merging.

COACH'S BOARD — THE PATTERN, STEP BY STEP

SPLIT, THEN MERGEPATTERN · MERGE SORTnums = [5, 2, 3, 1]

STEP 1

nums = [5, 2, 3, 1]. Split down to single elements, then merge sorted runs back together.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/sort-an-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        def merge_sort(arr: List[int]) -> List[int]:
            if len(arr) <= 1:
                return arr
            mid = len(arr) // 2
            left = merge_sort(arr[:mid])
            right = merge_sort(arr[mid:])
            return merge(left, right)

        def merge(left: List[int], right: List[int]) -> List[int]:
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    result.append(right[j])
                    j += 1
            result.extend(left[i:])
            result.extend(right[j:])
            return result

        return merge_sort(nums)

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 25 LN

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        for i in range(1, len(nums)):
            key = nums[i]
            j = i - 1
            while j >= 0 and nums[j] > key:  # slide bigger values right
                nums[j + 1] = nums[j]
                j -= 1
            nums[j + 1] = key
        return nums

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int[] sortArray(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }
        int[] aux = new int[nums.length];
        mergeSort(nums, aux, 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] nums, int[] aux, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, aux, lo, mid);
        mergeSort(nums, aux, mid + 1, hi);
        merge(nums, aux, lo, mid, hi);
    }

    private void merge(int[] nums, int[] aux, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++) {
            aux[k] = nums[k];
        }
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                nums[k] = aux[j++];
            } else if (j > hi) {
                nums[k] = aux[i++];
            } else if (aux[i] <= aux[j]) {
                nums[k] = aux[i++];
            } else {
                nums[k] = aux[j++];
            }
        }
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 38 LN

class Solution {
    public int[] sortArray(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int key = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = key;
        }
        return nums;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED