Consider the following comparison sorting algorithms:

i. Merge Sort

ii. Quick Sort

iii. Heap Sort

iv. Insertion Sort

Which of the following(s) is/are optimal comparison sorts?

A)i, ii and iii

B)i and iii

C)i, ii and iv

D)i, iii and iv

Consider the following comparison sorting algorithms:

i. Merge Sort

ii. Quick Sort

iii. Heap Sort

iv. Insertion Sort

Which of the following(s) is/are optimal comparison sorts?

A)i, ii and iii

B)i and iii

C)i, ii and iv

D)i, iii and iv

B. Since all this sort are O(nlognn). But in insertion sort and quick sort need O(n^2) in worst case

Mergesort runs in O(N log N) worst-case running time, and the number of comparisons used is nearly optimal. It is fine example of a recursive algorithm.

Quicksort is the fastest known generic sorting algorithm in practice. It’s average running time is O(N log N). It is very fast, mainly due to a very tight and highly optimized inner loop. It has O(N’2) worst case performanc, but this can be made exponentially unlikely with a little effort. By combining quicksort with heapsort, we can achieve quicksort’s fast running time on almost all inputs, with heapaort’s O(N log N) worst case running time.

Therefore the answer is A.