Question

Why is the insertion sort most efficient when the input list is almost in sorted order?

Answer 1

If the data is already sorted, Insertion Sort is the best choice for you as it will complete its operation in linear time.

Logic of Insertion sort:

for i -> 1 to input.length

j=i

while(j>0 && input[j]>input[j-1])

if(input[j]<input[j-1])

exchange(input[j],input[j-1],input)

j=j-1

end while

end for

In above case, loop will end just by doing a linear comparison at step i

@H¥DRA™