An array a[ ] of N elements is being sorted using the insertion sort algorithm.The algorithm is at the last stage,with the segment of the array in positions 0 through N-2 already sorted.How many array elements will a[N-1] have to be compared to,before it can be placed into its proper position?
A) Just one
B) Could be any number of elements between 1 and N-1 (inclusive.
C) Could be any number of elements between 1 and N (inclusive.
D) N-1

Question

Quizplus · Accepted Answer

In the worst case, a[N-1] could be smaller than all the elements in the sorted segment, requiring comparisons with all N-1 elements. In the best case, it could be larger than the last element of the sorted segment, requiring only one comparison.

An Array A[ ] of N Elements Is Being Sorted