GATE CS 2003 Q22 — Searching, Sorting, Hashing

In a standard array-based implementation of Insertion Sort, inserting the $i$-th element into a sorted subarray of size $i-1$ involves two main steps:

1. Finding the correct insertion position: Using binary search, we can locate the correct position in $O(\log i)$ time. Over $n$ iterations, the total search time is: $$\sum_{i=1}^{n} O(\log i) = O(n \log n)$$
2. Shifting the elements to make room: Since the elements are stored in a contiguous array, inserting an element at index $k$ requires shifting all elements from index $k$ to $i-1$ one position to the right. In the worst case (e.g., when the array is sorted in reverse order), we must shift all $i-1$ elements. Over $n$ iterations, the total shifting time is: $$\sum_{i=1}^{n} O(i) = \Theta(n^2)$$

The total worst-case running time is the sum of the search time and the shifting time:

Thus, using binary search reduces the number of comparisons but does not reduce the number of element movements. The overall worst-case running time remains $\Theta(n^2)$.