Awesome q2a theme
0 votes


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.
in Algorithms by (13 points) | 62 views

2 Answers

0 votes

Answer will be Option (C).

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)
0 votes
Option (4) is clearly false, the only other option stumbling block would’ve been the stable sort one, and the most obvious choice would’ve been quicksort, but it can be also made stable though increasing the complexity. Option (3) is true.

Therefore Only option 4 is genuinely false.
by (717 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,590 questions
2,831 answers
95,549 users