Question

Which of the following sorting algorithms run in worst-case (guaranteed) time on integers? Select all that apply.

a. Mergesort
b. Countingsort
c. Quicksort
d. Heapsort
e. Radixsort
Please select the correct option(s).

Answer 1

Mergesort, countingsort, and radixsort run in worst-case guaranteed time for sorting integers, with countingsort and radixsort offering linear time performance under certain conditions. Quicksort and heapsort do not have this guarantee.

Step-by-step explanation:

Among the sorting algorithms listed, mergesort, countingsort, and radixsort run in worst-case guaranteed time on integers. Here's why:

• Mergesort has a guaranteed running time of O(n log n) because it consistently divides the array in half, sorts each half, and then merges them back together.
• Countingsort is linear time sorting algorithm, O(n+k), ideal for integers when the range of input data (k) is not significantly larger than the number of elements to sort (n).
• Radixsort also runs in linear time, O(nk), for integers, relying on individual digits' sort to organize the entire number, where k is the maximum number of digits in the input integers.

Quicksort and Heapsort, while having good average-case performance, do not have guaranteed worst-case running time. Quicksort can degrade to O(n²), particularly when the pivot selection is poor, and Heapsort is O(n log n) in its best, average, and worst-case scenarios, but these are not considered as linear or guaranteed when compared to others.