UGC NET CSE | June 2019 | Part 2 | Question: 62

Question

There are many sorting algorithms based on comparison. The running time of heapsort algorithm is $O(n \text{lg}n)$. Like $P$, but unlike $Q$, heapsort sorts in place where $(P,Q)$ is equal to

• A. Merge sort, Quick sort
• B. Quick sort, insertion sort
• C. Insertion sort, Quick sort
• D. Insertion sort, Merge sort

Comments

2)

Heap sort and Quick sort are unstable sorting algorithm whereas Insertion sort is Stable sorting algorithm.

---

they have asked about in-place algo  and running time O(nlogn)

Answer 1

Answer should be (4) Insertion Sort, Merge Sort

Explanation - 

The question asks specifically for in-place sorting algorithms, which means the algorithms in which only $O(1)$ space is used. 

Hence, out of the options - 

Insertion Sort - Sorts in place with worst case time and space complexity of $O(n^2)$ and $O(1)$ respectively.

Heap Sort - Sorts in place with worst case time and space complexity of $O(n \cdot \log n)$ and $O(1)$ respectively.

Merge Sort - Sorts out of place with worst case time and space complexity of $O(n\cdot \log n)$ and $O(n)$ respectively. 

Quick Sort - Sorts in place with worst case time and space complexity of $O(n^2)$ and $O(1)$ respectively. 

 

Now for the given question, P needs to be an in place sorting algorithm, and Q needs to be out of place sorting algorithm, Hence option 4.

Answer 2

merge sort is in place complexity nlogn

where as quick sor worst case goes for o(n^2)