Sorting

Merge sort vs Heap sort

Merge sort and Heap sort both put an array in order, in different ways. Merge sort: divide and conquer: split, sort each half, merge. Heap sort: build a max-heap in the array, then repeatedly move the largest value to the end. In the worst case both take O(n log n), so the choice comes down to the other differences below.

At a glance

Property	Merge sort	Heap sort
Technique	Divide and conquer: split, sort each half, merge	Build a max-heap in the array, then repeatedly move the largest value to the end
Best case time	O(n log n)	O(n log n)
Average case time	O(n log n)	O(n log n)
Worst case time	O(n log n)	O(n log n)
Extra space	O(n)	O(1)
Stable (equal values keep their order)	Yes	No
In place (no extra array)	No	Yes
Needs sorted input	No	No

Choose merge sort when

you need a guaranteed O(n log n) time or a stable sort.

Avoid it when

memory is tight.

Choose heap sort when

you need a guaranteed O(n log n) time and almost no extra memory.

Avoid it when

you need a stable sort, or the fastest sort on typical data.

The same inputs, counted

These numbers come from running both real implementations: operations (comparisons plus writes, a swap counting as two writes).

Input	Merge sort	Heap sort
Mixed	34	43
Already sorted	31	53
Reversed	29	40
Nearly sorted	31	50
Duplicates	32	36

Merge sort vs Heap sort

At a glance

Choose merge sort when

Avoid it when

Choose heap sort when

Avoid it when

The same inputs, counted

See them run

More comparisons

Merge sort vs Heap sort

At a glance

When to choose each

Choose merge sort when

Avoid it when

Choose heap sort when

Avoid it when

The same inputs, counted

See them run

More comparisons