Sorting

Selection sort vs Heap sort

Selection sort and Heap sort both put an array in order, in different ways. Selection sort: repeatedly pick the smallest remaining value. Heap sort: build a max-heap in the array, then repeatedly move the largest value to the end. In the worst case heap sort takes O(n log n) while selection sort takes O(n²), so heap sort scales better on large inputs.

At a glance

Property	Selection sort	Heap sort
Technique	Repeatedly pick the smallest remaining value	Build a max-heap in the array, then repeatedly move the largest value to the end
Best case time	O(n²)	O(n log n)
Average case time	O(n²)	O(n log n)
Worst case time	O(n²)	O(n log n)
Extra space	O(1)	O(1)
Stable (equal values keep their order)	No	No
In place (no extra array)	Yes	Yes
Needs sorted input	No	No

Choose selection sort when

writing to memory is expensive, since it makes at most n - 1 swaps.

Avoid it when

the data is large, or you hope sorted input will be fast.

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	Selection sort	Heap sort
Mixed	29	43
Already sorted	21	53
Reversed	27	40
Nearly sorted	23	50
Duplicates	31	36

Selection sort vs Heap sort

At a glance

Choose selection sort when

Avoid it when

Choose heap sort when

Avoid it when

The same inputs, counted

See them run

More comparisons

Selection sort vs Heap sort

At a glance

When to choose each

Choose selection sort when

Avoid it when

Choose heap sort when

Avoid it when

The same inputs, counted

See them run

More comparisons