There are many sorting algorithms based on comparison. The running time of…

Key idea: identify which algorithms are in-place and which have O(n log n) time.

• Heapsort: runs in O(n log n) and sorts in place.

• Insertion sort: sorts in place, but its typical running time is O(n^2).

• Merge sort: runs in O(n log n) but the standard implementation is not in-place (it requires O(n) extra space).

• Quick sort: typically in-place and has average O(n log n) time, though worst-case time can be O(n^2).

Explanation: The clause "Like P, but unlike Q, heapsort sorts in place" compares the in-place property. Therefore P should be an in-place algorithm and Q should be a non-in-place algorithm. Among the listed algorithms, insertion sort is in-place and merge sort is not, so (P, Q) = (Insertion sort, Merge sort).

Note: Although merge sort shares the O(n log n) running time with heapsort, it is excluded by the in-place requirement; quick sort is in-place so it would not satisfy the "unlike Q" condition if chosen as Q.