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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,429 answers

195,207 comments

99,918 users