AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Easysortingspace

~60s

The sort that needs a buffer

Which of these comparison sorts needs O(n) auxiliary space in its usual array implementation?

Show the answer and the worked solution

Correct answer: C.

Merge sort

Worked solution

  1. Heapsort, insertion sort and selection sort all rearrange elements within the array and need only a fixed number of temporary variables.
  2. Merging two sorted runs cannot be done in place without a far more elaborate algorithm, so the standard implementation copies the runs into a scratch buffer.
  3. That buffer is as large as the segment being merged, which reaches n at the top level, so Merge sort is the one needing O(n) extra space.

Answer: Merge sort.

The idea

Merge sort trades memory for a guaranteed O(n log n) and for stability. Heapsort gives the same time bound in place but is unstable — there is no free lunch among the three properties.

Shortcut. Heapsort, insertion sort and selection sort all work in place with swaps; only merging needs a scratch buffer as long as the runs, O(n).

Common trap. "Heapsort" shares merge sort's O(n log n) guarantee, so it is assumed to share the memory cost, but it sorts in place.

Data Structures & Algorithms

28 of 40

Level

Easy

Target time

~60s

PreviousNext
AI InterviewGet started

The sort that needs a buffer — Aptitude Question

The sort that needs a buffer: Which of these comparison sorts needs O(n) auxiliary space in its usual array… Answer and worked solution on CodeKairo.

Question

Which of these comparison sorts needs O(n) auxiliary space in its usual array implementation?

Options

  1. Heapsort
  2. Insertion sort
  3. Merge sort
  4. Selection sort
Show the answer and the worked solution

Correct answer: C. Merge sort

Worked solution

  1. Heapsort, insertion sort and selection sort all rearrange elements within the array and need only a fixed number of temporary variables.
  2. Merging two sorted runs cannot be done in place without a far more elaborate algorithm, so the standard implementation copies the runs into a scratch buffer.
  3. That buffer is as large as the segment being merged, which reaches n at the top level, so Merge sort is the one needing O(n) extra space.

Answer: Merge sort.

The idea

Merge sort trades memory for a guaranteed O(n log n) and for stability. Heapsort gives the same time bound in place but is unstable — there is no free lunch among the three properties.

Shortcut. Heapsort, insertion sort and selection sort all work in place with swaps; only merging needs a scratch buffer as long as the runs, O(n).

Common trap. "Heapsort" shares merge sort's O(n log n) guarantee, so it is assumed to share the memory cost, but it sorts in place.

All Data Structures & Algorithms questions · placement mock tests