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. What usually goes wrong. What you see What caused it How to fix it --- --- --- StackOverflowError on any array longer than one A split produc

Challenge: Merge Sort an Array