Question

Which of the following is correct with regard to insertion sort?

(a) insertion sort is stable and it sorts In-place

(b) insertion sort is unstable and it sorts In-place

(c) insertion sort is stable and it does not sort In-place

(d) insertion sort is unstable and it does not sort In-place

I had been asked this question in an interview for internship.

My question is taken from Insertion sort in division Sorting of Data Structures & Algorithms II

Answer 1

The correct option is (a) insertion sort is stable and it sorts In-place

Easiest explanation - During insertion sort, the relative order of elements is not changed. Therefore, it is a stable sorting algorithm. And insertion sort requires only O(1) of additional memory space. Therefore, it sorts In-place.