title: How can I improve Insertionsort by the following argument ? The correct answer is b. Can someone CLEARLY explain every answer?
body: <p>A person claims that they can improve <code>InsertionSort</code> by the following argument. In the innermost loop of <code>InsertionSort</code>, instead of looping over all entries in the already sorted array in order to insert the j’th observed element, simply perform <code>BinarySearch</code> 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:</p>
  <p>a. <strong>True</strong>: In this version, the <code>while</code> loop will iterate <strong>log(n)</strong>, 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 <strong>log(n)</strong> in the worst case scenario. Adding up, Insertion Sort will significantly improve in this case to continue to require <strong>n log(n)</strong> in the worst case scenario like mergesort.</p>
  <p>b. <strong>False</strong>: In this version, the <code>while</code> loop will iterate <strong>log(n)</strong>, 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 <strong>n</strong> in the worst case scenario. Adding up, Insertion Sort will continue to require <strong>n²</strong> in the worst case scenario which is orders of magnitude worse than mergesort.</p>
  <p>c. <strong>False</strong>: In this version, the <code>while</code> loop will iterate <strong>n</strong>, 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 <strong>log(n)</strong> in the worst case scenario. Adding up, Insertion Sort will continue to require <strong>n log(n)</strong> in the worst case scenario which is orders of magnitude worse than mergesort.</p>
  <p>d. <strong>True</strong>: In this version, the <code>while</code> loop will iterate <strong>log(n)</strong>, 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 <strong>n</strong> in the worst case scenario. Adding up, Insertion Sort will continue to require <strong>n log(n)</strong> in the worst case scenario which is orders of magnitude worse than mergesort.</p>