Question

Statement 1: In insertion sort, after m passes through the array, the first m elements are in sorted order.

Statement 2: And these elements are the m smallest elements in the array.

(a) Both the statements are true

(b) Statement 1 is true but statement 2 is false

(c) Statement 1 is false but statement 2 is true

(d) Both the statements are false

I got this question during an online interview.

I need to ask this question from Insertion sort in section Sorting of Data Structures & Algorithms II

Answer 1

Right option is (b) Statement 1 is true but statement 2 is false

The best I can explain: In insertion sort, after m passes through the array, the first m elements are in sorted order but they are whatever the first m elements were in the unsorted array.