'How can I improve Insertionsort by the following argument ? The correct answer is b. Can someone CLEARLY explain every answer?

A person claims that they can improve InsertionSort by the following argument. In the innermost loop of InsertionSort, instead of looping over all entries in the already sorted array in order to insert the j’th observed element, simply perform BinarySearch in order to sandwich the j’th element in its correct position in the list A[1, ... , j−1]. This person claims that their resulting insertion sort is asymptotically as good as mergesort in the worst case scenario. True or False and why? Circle the one correct answer from the below:

a. True: In this version, the while loop will iterate log(n), but in each such iteration elements in the left side of the list have to be shifted to allow room for the key to propagate downwards across the median elements and so this shift will still require log(n) in the worst case scenario. Adding up, Insertion Sort will significantly improve in this case to continue to require n log(n) in the worst case scenario like mergesort.

b. False: In this version, the while loop will iterate log(n), but in each such iteration elements in the left side of the list have to be shifted to allow room for the key to propagate downwards and so this shift will still require n in the worst case scenario. Adding up, Insertion Sort will continue to require n² in the worst case scenario which is orders of magnitude worse than mergesort.

c. False: In this version, the while loop will iterate n, but in each such iteration elements in the left side of the list have to be shifted to allow room for the key to propagate downwards and so this shift will still require log(n) in the worst case scenario. Adding up, Insertion Sort will continue to require n log(n) in the worst case scenario which is orders of magnitude worse than mergesort.

d. True: In this version, the while loop will iterate log(n), but in each such iteration elements in the left side of the list have to be shifted to allow room for the key to propagate downwards and so this shift will still require n in the worst case scenario. Adding up, Insertion Sort will continue to require n log(n) in the worst case scenario which is orders of magnitude worse than mergesort.

while-looptime-complexitybig-omergesortinsertion-sort


Solution 1:[1]

b is correct, with some assumptions about compiler optimizations.

Consider a reverse sorted array,

8 7 6 5 4 3 2 1

and that insertion sort is half done so it is

5 6 7 8 4 3 2 1

The next step:

normal insertion sort sequence assuming most recent value read kept in register:

t = a[4] = 4                                     1 read
compare t and a[3]                               1 read 
a[4] = a[3] = 8                                          1 write
compare t and a[2]                               1 read
a[3] = a[2] = 7                                          1 write
compare t and a[1]                               1 read
a[2] = a[1] = 6                                          1 write
compare t and a[0]                               1 read
a[1] = a[0] = 5                                          1 write
a[0] = t = 4                                             1 write
                                                 ---------------
                                                 5 read  5 write

binary search

t = a[4]                                         1 read
compare t and a[1]                               1 read
compare t and a[0]                               1 read
a[4] = a[3]                                      1 read  1 write
a[3] = a[2]                                      1 read  1 write
a[2] = a[1]                                      1 read  1 write
a[1] = a[0]                                      1 read  1 write
a[0] = t                                                 1 write
                                                 ----------------
                                                 7 read  5 write

If a compiler re-read data with normal insertion sort it would be

                                                 9 read  5 write

In which case the binary search would save some time.

Solution 2:[2]

The expected answer to this question is b), but the explanation is not precise enough:

  • locating the position where to insert the j-th element indeed requires log(j) comparisons instead of j comparisons for regular Insertion Sort.
  • inserting the elements requires j element moves in the worst case for both implementations (reverse sorted array).

Summing these over the whole array produces:

  • n log(n) comparisons for this modified Insertion Sort idea in all cases vs: n2 comparisons in the worst case (already sorted array) for the classic implementation.
  • n2 element moves in the worst case in both implementations (reverse sorted array).
  • note that in the classic implementation the sum of the number of comparisons and element moves is constant.

Merge Sort on the other hand uses approximately n log(n) comparisons and n log(n) element moves in all cases.

Therefore the claim the resulting insertion sort is asymptotically as good as mergesort in the worst case scenario is False, indeed because the modified Insertion Sort method still performs n2 element moves in the worst case, which is asymptotically much worse than n log(n) moves.

Note however that depending on the relative cost of comparisons and element moves, the performance of this modified Insertion Sort approach may be much better than the classic implementation, for example sorting an array of string pointers containing URLs to the same site, the cost of comparing strings with a long initial substring is much greater than moving a single pointer.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 chqrlie

Related Questions