DSA interview question

Insertion Sort

Easy · Algorithms · Topics: sorting, algorithm

The problem

Think of how you sort a hand of playing cards: you pick up one card at a time and slide it left into its correct place among the cards you're already holding. That's insertion sort. It's O(n²) in the worst case, but on data that's almost sorted it runs in close to linear time, because each new element only moves a few places. That's why real-world sorting libraries (introsort, TimSort) switch to insertion sort for small or nearly-sorted pieces.

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

Function signature

long long insertionSort(vector<int>& a);  // sorts in place; returns the number of shifts performed

Test cases

Input `a`	Output	Shifts	Explanation
`[12, 11, 13, 5, 6]`	`[5, 6, 11, 12, 13]`	7	One shift per inversion
`[5, 2, 9, 1, 5, 6]`	`[1, 2, 5, 5, 6, 9]`	6	Stable: the two 5s keep their order
`[1, 2, 3, 4]`	`[1, 2, 3, 4]`	0	Already sorted: O(n)
`[1, 2, 4, 3, 5]`	`[1, 2, 3, 4, 5]`	1	Nearly sorted: almost no work
`[4, 3, 2, 1]`	`[1, 2, 3, 4]`	6	Reverse order: n(n − 1)/2 shifts
`[]`	`[]`	0

(Confirm: sort in place, non-decreasing; the shift count equals the number of inversions; the code also cross-checks 1,000 random arrays against std::sort.)

How interviewers phrase it

"Implement insertion sort."
"Which simple sort would you use for nearly sorted data, and why?"
"Why do library sorts use insertion sort for small subarrays?"

Clarifying questions to ask

Ascending? In place?
Is the data nearly sorted? (That's where insertion sort shines.)
Does stability matter?

Follow-ups to expect

"What's the best case?"
"How does the running time relate to inversions?"
"Is it stable?"
"Why is it used inside quicksort or TimSort?"
"What's an online algorithm?"

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