5. Insertion sort can be improved by using binary search to find the next insert

Question

5. Insertion sort can be improved by using binary search to find the next insertion point. However, this does not change the overall complexity of the algorithm. Why? 6. The standard quick sort algorithm is O(n') in the worst case. What is the worst case? What modifications can be made to the algorithm to provide better behavior in this case? 7. If you were required to sort a very large file that would not fit in memory, what algorithm would you choose? Describe the steps you would perform to sort the file.

Explanation / Answer

Hi Dear,

As per the chegg guideline, please post one Question in a post.

I have answered Q5.

We can use binary search to reduce the number of comparisons in normal insertion sort. Binary Insertion Sort find use binary search to find the proper location to insert the selected item at each iteration.
In normal insertion, sort it takes O(i) (at ith iteration) in worst case.
we can reduce it to O(logi) by using binary search.

The algorithm as a whole still has a running worst case running time of O(n^2) because of the series of swaps required for each insertion.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.