Sorting

Selection sort vs Insertion sort

Selection sort and Insertion sort both put an array in order, in different ways. Selection sort: repeatedly pick the smallest remaining value. Insertion sort: insert each value into a sorted prefix. In the worst case both take O(n²), so the choice comes down to the other differences below.

At a glance

Property	Selection sort	Insertion sort
Technique	Repeatedly pick the smallest remaining value	Insert each value into a sorted prefix
Best case time	O(n²)	O(n)
Average case time	O(n²)	O(n²)
Worst case time	O(n²)	O(n²)
Extra space	O(1)	O(1)
Stable (equal values keep their order)	No	Yes
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 insertion sort when

the array is small or nearly sorted.

Avoid it when

the array is large and in random order.

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	Insertion sort
Mixed	29	30
Already sorted	21	12
Reversed	27	48
Nearly sorted	23	14
Duplicates	31	36

Selection sort vs Insertion sort

At a glance

Choose selection sort when

Avoid it when

Choose insertion sort when

Avoid it when

The same inputs, counted

See them run

More comparisons

Selection sort vs Insertion sort

At a glance

When to choose each

Choose selection sort when

Avoid it when

Choose insertion sort when

Avoid it when

The same inputs, counted

See them run

More comparisons