Sorting

Merge sort vs Quick sort

Merge sort and Quick sort both put an array in order, in different ways. Merge sort: divide and conquer: split, sort each half, merge. Quick sort: divide and conquer: partition around a pivot. In the worst case merge sort takes O(n log n) while quick sort takes O(n²), so merge sort scales better on large inputs.

At a glance

Property	Merge sort	Quick sort
Technique	Divide and conquer: split, sort each half, merge	Divide and conquer: partition around a pivot
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²)
Extra space	O(n)	O(log n)
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 quick sort when

you want a fast in-place sort on typical data.

Avoid it when

you need a worst-case guarantee or a stable sort.

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	Quick sort
Mixed	34	31
Already sorted	31	75
Reversed	29	51
Nearly sorted	31	65
Duplicates	32	29

Merge sort vs Quick sort

At a glance

Choose merge sort when

Avoid it when

Choose quick sort when

Avoid it when

The same inputs, counted

See them run

More comparisons

Merge sort vs Quick sort

At a glance

When to choose each

Choose merge sort when

Avoid it when

Choose quick sort when

Avoid it when

The same inputs, counted

See them run

More comparisons