Main Page

Previous Page
Next Page

[Page 995 (continued)]

Answers to Self-Review Exercises


a) 16, because an O(n2) algorithm takes 16 times as long to sort four times as much information. b) O(n log n).


Both of these algorithms incorporate "halving"somehow reducing something by half. The binary search eliminates from consideration one-half of the vector after each comparison. The merge sort splits the vector in half each time it is called.


The insertion sort is easier to understand and to implement than the merge sort. The merge sort is far more efficient (O(n log n)) than the insertion sort (O(n2)).


In a sense, it does not really sort these two subvectors. It simply keeps splitting the original vector in half until it provides a one-element subvector, which is, of course, sorted. It then builds up the original two subvectors by merging these one-element vectors to form larger subvectors, which are then merged, and so on.

Previous Page
Next Page