Put an X in the column that describes its behavior. In each case n represents the number of data items to be sorted.
| O(n) | O(n lg n) | O(n^2)
---------------|------|-----------|-------- Bubble Sort | | | Insertion Sort | | | Merge Sort | | | Bucket sort | | |
-
Which of the sorts listed above are guaranteed to be very fast ( O(n) ) on lists that are already sorted?
-
Which of the sorts listed above are guaranteed to be ( O(n lg n) ) or better on all long lists?
-
What is the limitation on the Bucket sort that restricts its use?
-
If a Bubble sort takes 3 seconds to sort 5,000 items on a certain computer system, estimate how long it will take to sort 20,000 items.
-
If a Merge sort takes 15 µseconds to sort 32,000 items on a certain computer system, estimate how long it will take to sort 64,000 items.