83. Merge Sort

Given an array of n integers, sort it in ascending order using the merge sort algorithm (divide the array in half, recursively sort each half, then merge the two sorted halves) and print the result.

Input: The first line contains an integer n. The second line contains n space-separated integers, the array to sort. Output: Print the sorted array in ascending order, space-separated, on one line.

1 <= n <= 10^5

Merge sort is a 'stable' sort by nature (equal elements keep their relative order during merging, as long as you pick from the LEFT half first on ties) - this is exactly why it's a common building block for stability-sensitive problems like the previous 'Sort by Set Bit Count' problem.

Split a big, messy pile of papers in half, then split each half in half again, and keep splitting until every pile has just one paper (which is trivially 'sorted' on its own). Then carefully merge pairs of small sorted piles back together into bigger sorted piles, all the way back up to one fully sorted pile. Brute force: A simple sort like insertion sort or bubble sort works by repeatedly comparing and shifting ADJACENT elements, which costs O(n²) in the worst case since progress is made one small step at a time. Optimised: By splitting the problem in half recursively, merge sort does O(n) work to combine two already-sorted halves at EACH of the roughly log(n) levels of splitting, giving O(n log n) total - genuinely faster than O(n²) approaches for large inputs, and importantly, this performance is GUARANTEED regardless of the input's original order (unlike quicksort, which can degrade on unlucky inputs).

Pick a pivot element, partition the array in place so everything less than the pivot comes before it and everything greater comes after, then recursively apply the same process to the two partitions. On average this halves the problem size at each level of recursion, giving strong practical performance and no auxiliary array, but a poor pivot choice (e.g. an already-sorted array with a naive first-element pivot) degrades it to quadratic time in the worst case, and it isn't stable. Time: O(n log n) average, O(n^2) worst case Space: O(log n)

Repeatedly compare adjacent (or nearby) elements and swap them into order, sweeping through the array over and over until no more swaps are needed (bubble sort), or build up a sorted prefix one element at a time by inserting each new element into its correct position among those already sorted (insertion sort). Both are simple, in-place, and easy to verify correct, but their nested-loop structure makes them quadratic, which is far too slow for n up to 10^5. Time: O(n^2) Space: O(1)

Recursively split the array into two halves, sort each half independently by the same recursive process, and merge the two sorted halves together in linear time by walking them with two pointers. This guarantees O(n log n) time in every case, not just on average, because the divide step always halves the problem regardless of the input's arrangement, and it's naturally stable (equal elements from the left half are placed before equal elements from the right half during merge), making it the reliable choice for large or adversarial inputs, at the cost of needing auxiliary space for merging. Time: O(n log n) Space: O(n)

1. Split the array into two roughly equal halves. 2. Recursively apply this exact same splitting process to each half, until every piece is down to a single element. 3. Merge two sorted single-element pieces into one sorted pair, by comparing and picking the smaller first. 4. Keep merging sorted pieces back together, pair by pair, until you're left with one single, fully sorted array.

Time: n times log n, in EVERY case (best, average, and worst) - merge sort's defining strength is this consistency, unlike quicksort's occasional worst-case slowdown. Space: O(n) extra space, needed for the temporary arrays used during each merge step - this is merge sort's main trade-off against quicksort's in-place, O(log n)-space approach.

n = 1 (a single element, trivially sorted); n = 10^5 to confirm O(n log n) performance; duplicate values, which aren't excluded by the constraints.

Be ready to state merge sort's guaranteed O(n log n) worst case as its key advantage over quicksort, and its O(n) extra space requirement as its key disadvantage - this exact comparison is asked extremely often.