584 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

edited | 584 views
0
2)

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

+1 vote
merge sort is in place complexity nlogn

where as quick sor worst case goes for o(n^2)
+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.