##### GATE 2003 Example on Insertion Sort

The unusual \(\Theta(n^2)\) implementation of Insertion Sort to sort an array uses linear search to identify the position where and

element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position,

the worst case running time will be:

A) Remains \(\Theta(n^2)\)

B) become \(\Theta(n(\log n)^2)\)

C) become \(\Theta(n)\)

d) become \(\Theta(n\log n)\)

```
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
```

Consider, Intermediate state of Array (containing numbers) while the execution of insertion sort :

{Here, numbers to the left of number-0 are sorted }

__When linear search is used__

Time to find the correct position of *key *: \(\Theta(n)\)

Time to move the elements to make space for key : \(\Theta(n)\)

Total elements = n

\(\therefore Total\ \ Time = n(\Theta(n) + \Theta(n)) = \Theta(n^2)\)

__When binary search is used__

Time to find the correct position of *key : *\(\Theta(\log n)\)

Time to move the elements in the array to make space for *key *: \(\Theta(n)\)

Total elements = \(n\)

\(\therefore Total \ \ Time = n(\Theta(\log n) + \Theta(n)) = \Theta(n^2)\)

Hence, Although we made impovement over the searching for the position of the **key**,** **but we still need to move the elements which'll take the same time \(\Theta(n)\). Therefore the total time remains same i.e \(\Theta(n^2)\)

Ans **(A)**