Query on sorting techniques


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.