Sorting

Insertion sort vs Merge sort

Insertion sort and Merge sort both put an array in order, in different ways. Insertion sort: insert each value into a sorted prefix. Merge sort: divide and conquer: split, sort each half, merge. In the worst case merge sort takes O(n log n) while insertion sort takes O(n²), so merge sort scales better on large inputs.

At a glance

Property	Insertion sort	Merge sort
Technique	Insert each value into a sorted prefix	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)	Yes	Yes
In place (no extra array)	Yes	No
Needs sorted input	No	No

Choose insertion sort when

the array is small or nearly sorted.

Avoid it when

the array is large and in random order.

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	Insertion sort	Merge sort
Mixed	30	34
Already sorted	12	31
Reversed	48	29
Nearly sorted	14	31
Duplicates	36	32

Insertion sort vs Merge sort

At a glance

Choose insertion sort when

Avoid it when

Choose merge sort when

Avoid it when

The same inputs, counted

See them run

More comparisons

Insertion sort vs Merge sort

At a glance

When to choose each

Choose insertion sort when

Avoid it when

Choose merge sort when

Avoid it when

The same inputs, counted

See them run

More comparisons