Recursive Sorting: Merge Sort

Part of: Recursion

Divide and Conquer Merge sort is the textbook example of recursive divide and conquer . It works in three stages: - Divide : split the array into two halves. - Conquer : recursively sort each half. - Combine : merge the two sorted halves into one sorted result. The base case is an array (or sub-array) of length 0 or 1, it is already sorted, so we stop. The Merge Step Merging two sorted lists is the heart of the algorithm. Walk both lists with pointers, repeatedly taking the smaller front element: Putting It Together Note: Arrays.copyOfRange is a convenience method beyond the AP Java Quick Reference. AP presents merge sort using one array with low, mid, and high indices rather than returned copies, so you are expected to trace this algorithm, not write it in this exact form. Why It Is Efficient The array is halved log n times, and each level does O(n) merging work, giving O(n log n) overall, far better than the O(n^2) of simple sorts on large inputs. Merge sort is also stable (equal elements keep their order) thanks to the <= in the merge. The Recursive Shape Notice the two recursive calls (mergeSort(left) and mergeSort(right)), branching recursion again, but here each branch handle

Challenge: Merge Sort an Array