Write a recursive implementation of Insertion Sort.

Question

Insertion sort using recursion

Answer 1

Hmm. Insertion sort is constantly inserting the element at the correct location in the already sorted part. It does not really lend itself to a recursive implementation, but here's a shot. Base case would be a list of size 1 (or 0). In that case, the list is sorted and is returned. Otherwise, recursively sort everything but the first (or last) element. Finally, insert that element into its proper place in the sorted collection.

With that said, how you choose to do it in reality is more of a problem with what type of collection you are dealing with and what are the space / time restrictions (also if the sort needs to be stable). Cheers!