Sorting

Selection sort vs Merge sort

Selection sort and Merge sort both put an array in order, in different ways. Selection sort: repeatedly pick the smallest remaining value. Merge sort: divide and conquer: split, sort each half, merge. In the worst case merge sort takes O(n log n) while selection sort takes O(n²), so merge sort scales better on large inputs.

At a glance

Property	Selection sort	Merge sort
Technique	Repeatedly pick the smallest remaining value	Divide and conquer: split, sort each half, merge
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(n)
Stable (equal values keep their order)	No	Yes
In place (no extra array)	Yes	No
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 merge sort when

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

Avoid it when

memory is tight.

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	Merge sort
Mixed	29	34
Already sorted	21	31
Reversed	27	29
Nearly sorted	23	31
Duplicates	31	32

Selection sort vs Merge sort

At a glance

Choose selection sort when

Avoid it when

Choose merge sort when

Avoid it when

The same inputs, counted

See them run

More comparisons

Selection sort vs Merge sort

At a glance

When to choose each

Choose selection sort when

Avoid it when

Choose merge sort when

Avoid it when

The same inputs, counted

See them run

More comparisons