Given an array of integers nums, sort the array in ascending order using the Merge Sort algorithm — recursively split the array in half until each piece is a single element (trivially sorted), then merge sorted pairs back together in linear time.
nums = [8,4,3,7,6][3,4,6,7,8]Merging two already-sorted sequences takes only O(n) — a single linear scan that compares the fronts of each side and copies the smaller one across. There are O(log n) levels of splitting (each level halves the range), so total work is O(n log n) — in the best, average, and worst case alike, unlike Quick Sort's adversarial O(n²). Merge Sort is also stable (the left[i] <= right[j] tie-break keeps equal elements in their original relative order) but not in-place — every merge needs an auxiliary buffer to hold a snapshot of both halves before overwriting them, which is the classic time/space tradeoff versus Quick Sort's O(log n) average auxiliary space.
Quadratic sorts are fine for small inputs only. Merge sort splits the work in half again and again.
Split the array into two halves. Sort each half recursively, until a part has only one element, which is already sorted. Then merge two sorted halves, by repeatedly taking the smaller front element. Merging two parts costs time proportional to their total length. There are log n levels of halving, so the total is O(n log n).
Split, sort halves, merge by taking the smaller front. Guaranteed O(n log n), at the cost of extra memory.
Run the animation above on your own input, or watch the 1:41 video explanation of Merge Sort with a dry run and Java code.