GATE CSE 2003 | Question: 22

Question

The usual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an 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

• A. remain $\Theta(n^2)$
• B. become $\Theta(n  (\log n)^2)$
• C. become $\Theta(n \log n)$
• D. become $\Theta(n)$

Comments

Both vanilla insertion sort and binary insertion sort gives us O($n^{2}$)

---

Concept:

• Insertion Sort = Insert each element into sorted part.

• Two steps per insertion:

  1. Find position → Binary Search = O(log⁡n)

  2. Shift elements → Still O(n)

Total Worst Case Time:

• Search: O(nlog⁡n)

• Shifting: O(n^2)

• Overall: Θ(n²)

✅ Correct Option: A. remain Θ(n²)

Note: Binary search reduces comparisons, not shifts.

---

A simple question to ask yourself : If using binary search would have made the sorting faster then why are we using linear search in first place ?

Answer 1

In insertion sort, with linear search, it takes

(worst case) $n$ comparisons for searching the right position, and $n$ swaps to make room to place the element.

Hence for n elements, a total of $n\times(n+n)$; $n$ for search and $n$ for swaps.

$= \Theta (2n^2) = \Theta (n^2)$

If we replace it with binary search, it takes

(worst case) $\log n$ comparisons for searching the right position, and $n$ swaps to make room to place the element.

Hence for n elements, a total of $n\times(\log n+n)$; $n$ for search and $n$ for swaps.

$= \Theta (n \times \log n + n^2) = \Theta (n^2)$

Hence, answer is A.

Comments

If we perform B-search instead of linear search( basically we are finding out the right positions in log n time) , no of swaps will be 1 each time. For n elements we will have n swaps in total .Isn't it ?

---

Source: https://en.wikipedia.org/wiki/Insertion_sort

---

Then, what will be the number of comparisons in best case? as n X ((n-1) + 0) will again you O(n^2)…. Pl clarify.

Answer 2

A. Complexity remains same.θ(n²)

To place the element x in the correct position first we are finding its correct position in the sorted array using binary search but we have to make the space for it by shifting all elements to the right, which in worst case may be equal to the size of the sorted array.

Answer 3

Vanilla insertion sort aur binary insertion sort dono sorting algorithms hain, lekin dono mein fark unka comparison karne ka tareeqa hai. Yeh rahi inki details:

1. Vanilla Insertion Sort

• Working: Har element ko uski sahi position par dalte hain, pehle wale sorted part ko ek-ek karke compare karke.
• Steps:
  • Array ka ek portion (shuru se) sorted hota hai.
  • Agla element uthao, sorted part ke saath compare karo, aur usse uski sahi jagah par insert karo.
• Time Complexity:
  • Best Case: O(n) (Agar array already sorted ho).
  • Worst Case: O(n2)(Reverse sorted array ke liye).

2. Binary Insertion Sort

• Working: Ismein bhi insertion sort ki tarah elements ko sorted part mein dalte hain, lekin comparison ke liye binary search ka use hota hai.
• Steps:
  • Agla element uthao, aur uske liye sorted part mein binary search se sahi position dhoondo.
  • Us position par element insert karo.
• Time Complexity:
  • Binary search ki wajah se comparison ka time O(logn) hota hai.
  • Best Case: O(nlog⁡n).
  • Worst Case: O(n2) (Shift karne ka cost same hai as vanilla insertion sort).

Farak:

• Vanilla insertion sort linear search karta hai (one by one compare karta hai).
• Binary insertion sort binary search karta hai, isliye comparison fast hoti hai, lekin shifting time dono mein same hota hai.

Dono ka use chhoti arrays ke liye theek hota hai, lekin bade data sets ke liye merge sort ya quick sort better hote hain.

Comments

Accha explanation hai. Thanks.

---

@Kshitij Sharma kya is question ka core number of comparisons pe na hoke number of swaps hai.

Kyonki comparisons to logn honge magar swaps worst case mein n honge.

For example 

1 , 2 , 3 ,4 ,5 ,6 ,7 | 0 (sirf 0 sort karne ke liye bacha hai)

To agar linear search karenge, to comparison 7 honge and swaps bhi 7 honge.

Wahin binary search mein comparison log7 honge magar kyonki worst case hai to swap 7 honge. Sabhi elements ek index aage badhenge.

And n elements ke liye ye n quare rahega. Yahan lar binary search ne index finding time to kam kardiya magar swaps to tab bhi utne hi rahenge. 

Kya ya sahi hai?