P = [1, 2, 3, 5, 4] Two sorting algo Binary sort (BS), Insertion sort (IS) apply. Let N1 be the total number of comparisons done by BS on the element of P and N2 be the total number of comparisons done by IS on the elements of P. Which of the following option is/are correct?

The correct options are:
1. IS on P perform only one swap.
2. N₁ > N₂
3. Both BS and IS on P will make at least one unnecessary comparison. (i.e. comparing element that are already in correct order)

Let us analyze the behavior of both Insertion Sort (IS) and Binary Insertion Sort (BS) on the array P = [1, 2, 3, 5, 4] step-by-step.

1. Insertion Sort (IS) Analysis:
Initially, the sorted subarray is [1]. We insert elements one by one:
- Insert 2: We compare 2 with 1. Since 2 > 1, no swap is needed. Subarray becomes [1, 2]. (Comparisons = 1, Swaps = 0)
- Insert 3: We compare 3 with 2. Since 3 > 2, no swap is needed. Subarray becomes [1, 2, 3]. (Comparisons = 1, Swaps = 0)
- Insert 5: We compare 5 with 3. Since 5 > 3, no swap is needed. Subarray becomes [1, 2, 3, 5]. (Comparisons = 1, Swaps = 0)
- Insert 4: We compare 4 with 5. Since 4 < 5, we swap 4 and 5. Next, we compare 4 with 3. Since 4 > 3, we stop. Subarray becomes [1, 2, 3, 4, 5]. (Comparisons = 2, Swaps = 1)

Thus, for Insertion Sort:
Total number of comparisons, N₂ = 1 + 1 + 1 + 2 = 5
Total number of swaps = 1 (only swapping 4 and 5)
This confirms the option: IS on P perform only one swap.

2. Binary Insertion Sort (BS) Analysis:
Binary Insertion Sort uses binary search to find the correct insertion position within the sorted prefix.
- Insert 2 into [1]: Search range is index [0, 0].
We compare 2 with index 0 (value 1). Since 2 > 1, position is found. (Comparisons = 1)
- Insert 3 into [1, 2]: Search range is index [0, 1].
First, mid is index 0 (value 1). We compare 3 with 1. Since 3 > 1, search range becomes [1, 1].
Next, mid is index 1 (value 2). We compare 3 with 2. Since 3 > 2, position is found. (Comparisons = 2)
- Insert 5 into [1, 2, 3]: Search range is index [0, 2].
First, mid is index 1 (value 2). We compare 5 with 2. Since 5 > 2, search range becomes [2, 2].
Next, mid is index 2 (value 3). We compare 5 with 3. Since 5 > 3, position is found. (Comparisons = 2)
- Insert 4 into [1, 2, 3, 5]: Search range is index [0, 3].
First, mid is index 1 (value 2). We compare 4 with 2. Since 4 > 2, search range becomes [2, 3].
Next, mid is index 2 (value 3). We compare 4 with 3. Since 4 > 3, search range becomes [3, 3].
Next, mid is index 3 (value 5). We compare 4 with 5. Since 4 < 5, position is found. (Comparisons = 3)

Thus, for Binary Insertion Sort:
Total number of comparisons, N₁ = 1 + 2 + 2 + 3 = 8

Comparing the two comparison counts:
Since N₁ = 8 and N₂ = 5, we have:
N₁ > N₂
This confirms the option: N₁ > N₂.

3. Unnecessary Comparisons:
An unnecessary comparison occurs when we compare elements that are already in their correct relative order.
- In IS, comparing 2 with 1, 3 with 2, and 5 with 3 are comparisons of elements already in correct order.
- In BS, binary search performs comparisons such as comparing 3 with 1, which are also already in correct order.
Thus, both algorithms make at least one unnecessary comparison.