Merge Sort

Sort the array ascending by implementing merge sort yourself (don't call the standard library sort).

Merge sort is the classic example of divide and conquer: split the problem into smaller subproblems (divide), solve each recursively (conquer), then combine the results (here, merge two sorted halves into one).

mergeSort(nums)

Input format: space-separated integers. Output the sorted values.

Examples

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

Walkthrough

Thinking it through

Sorting a large, arbitrary list directly is hard to reason about — too many orderings to compare pairwise without waste (why naive approaches like repeatedly scanning for the smallest remaining element cost roughly n²). Merge sort's insight: sorting is easy if you already have two smaller sorted pieces, since combining two sorted sequences is efficient and mechanical.

The combining step: merging two sorted halves

Given two already-sorted lists, combine them by repeatedly comparing the smallest remaining element of each and taking the smaller — advancing through both in lockstep. Since both are internally ordered, this always picks the true next-smallest overall. Touching each element once, merging two halves totaling n takes O(n).

Divide and conquer: getting two sorted halves in the first place

You start with one unsorted list, not two sorted halves — so split it into two roughly equal halves and sort each the same way, recursively. Splitting stops at zero or one elements (already sorted — the base case). Once both halves are recursively sorted, merge them in O(n).

Why this ends up faster than simpler approaches

Each level of splitting doubles the pieces and halves their size, and merging work per level still totals O(n) (linear in combined size). Halving a list of size n down to size 1 takes about log n levels. Total work: roughly O(n) per level × O(log n) levels = O(n log n) — meaningfully faster than O(n²) as lists grow.

Why divide and conquer is the right lens

Split a hard problem into smaller structurally-identical subproblems, solve recursively, combine cheaply — that's divide and conquer. It works whenever combining already-solved subproblems is cheap (linear merging here) even though solving the whole problem directly isn't.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.