Recursive Insertion and Putting It Together

Part of: Recursion

Insertion Sort, Recursively. We usually write insertion sort with loops, but it also has an elegant recursive form that reinforces the base case + smaller problem mindset. The idea: to sort the first n elements, first recursively sort the first n-1 , then insert the n-th element into its correct spot among the already-sorted prefix. Here the recursive call comes first (sort the prefix), then the insert work happens on the way back up the stack. Comparing the Two Sorts. - Merge sort : divide and conquer, O(n log n) , uses extra arrays. - Insertion sort : builds a sorted prefix one element at a time, O(n^2) in the worst case, but fast on nearly-sorted data and sorts in place. Both illustrate the same recursive principle: solve a smaller version, then do a little local work. What usually goes wrong. What you see What caused it How to fix it --- --- --- The array comes back almost sorted, with the earliest elements wrong The insert work ran before the recursive call, so it was placing values into a prefix nobody had sorted yet Recurse first, then insert on the way back up StackOverflowError The recursive call passed n instead of n minus 1 Shrink the range by exactly one element per cal

Challenge: Recursive Insertion Sort