DSA interview question

Recursive Insertion Sort

Easy · Algorithms · Topics: sorting, recursion

The problem

The recursion chapter of a teaching platform needs insertion sort written without an outer loop. Insertion sort has a naturally recursive shape: to sort the first n elements, sort the first n − 1, then insert the n-th element into its place. Writing it this way makes the algorithm's invariant (the prefix is always sorted) explicit in the code, and it's good practice in identifying what the recursive call guarantees before you use its result.

Example: [12, 11, 13, 5, 6] → [5, 6, 11, 12, 13].

Function signature

void recursiveInsertionSort(vector<int>& a, int n);  // sorts the first n elements; call with a.size()

Test cases

Input `a`	Output	Explanation
`[12, 11, 13, 5, 6]`	`[5, 6, 11, 12, 13]`
`[5, 2, 9, 1, 5, 6]`	`[1, 2, 5, 5, 6, 9]`	Stable for equal values
`[1, 2, 3, 4]`	`[1, 2, 3, 4]`	Each insertion is a single comparison
`[4, 3, 2, 1]`	`[1, 2, 3, 4]`	Every insertion shifts the whole prefix
`[42]`	`[42]`	Base case
`[]`	`[]`

(Confirm: in-place, non-decreasing; the code cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

"Implement insertion sort using recursion."
"Recursively sort the first n − 1 elements, then insert the last one."

Clarifying questions to ask

Replace only the outer loop, or also the shifting loop?
How large can n be? (Recursion depth n.)
Ascending order?

Follow-ups to expect

"What does the recursive call guarantee?"
"Why recurse first and insert afterwards?"
"Is it still stable?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview