62 views

Which of the following is not true about comparison-based sorting algorithms.

1. The minimum possible time complexity of a comparison-based sorting algorithm is O(N log N) for a random input array.
2. Any comparison-based sorting algorithm can be made stable by using the position as a criteria when two elements are compared.
3. Counting Sort is not a comparison-based sorting algorithm.
4. Heap Sort is not a comparison-based sorting algorithm.

Choose the correct option.

1. 1,2.
2. 2,4.
3. 4.
4. 2.
| 62 views

1. Yes, Best possible Time Complexity for "Comparison based" Sorting Algorithm is $\Omega(N log N)$. It's proof is based on number of permutations we can get. You can read here.

2. Yes, we can certainly implement so that stability is guaranteed even though the default procedure don't. We might increase time complexity, but, it's certainly possible.

3. Yes, Counting Sort is NOT comparison based sorting Algorithm.

4. No, Heap Sort is comparison based. We compare in the heapify function.

So, Option (C).

by (2.5k points)