The Gateway to Computer Science Excellence
+3 votes
217 views

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

  1. Merge sort, Quick sort
  2. Quick sort, insertion sort
  3. Insertion sort, Quick sort
  4. Insertion sort, Merge sort
in Algorithms by Veteran (424k points)
edited by | 217 views
0
2)

Heap sort and Quick sort are unstable sorting algorithm whereas Insertion sort is Stable sorting algorithm.
0
they have asked about in-place algo  and running time O(nlogn)

2 Answers

+1 vote
merge sort is in place complexity nlogn

where as quick sor worst case goes for o(n^2)
by (159 points)
+1 vote

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.

by Active (1.6k 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
50,648 questions
56,429 answers
195,207 comments
99,918 users