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. The Big Picture of Recursion Across this unit you have seen one pattern repeat: - Identify a base case where the answer is trivial. - Express the problem in terms of a smaller version of itself. - Let the call stack combine the partial results. Whether reversing a string, searching a sorted array, or sorting with merge or insertion, recursion turns a hard problem into the same problem, one step smaller . Mastering t

Challenge: Recursive Insertion Sort