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

The Gateway to Computer Science Excellence

+3 votes

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

- Merge sort, Quick sort
- Quick sort, insertion sort
- Insertion sort, Quick sort
- Insertion sort, Merge sort

+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.

52,345 questions

60,517 answers

201,937 comments

95,367 users