Skip to interview prep
Apexed

33. Compare the common sorting algorithms.

MediumSorting

Technical
Show model answer

Bubble, selection and insertion sort are O(n²); insertion sort is fast on small or nearly sorted input and is stable. Merge sort is O(n log n) always, stable, and uses O(n) extra space. Quicksort averages O(n log n), is in place, but worst-case O(n²). Heap sort is O(n log n) in place but not stable.

Counting, radix and bucket sort beat O(n log n) by not comparing elements, but only for restricted inputs (small integer ranges or uniform distributions). Comparison sorts cannot beat Ω(n log n) in the worst case.

Compare the common sorting algorithms. — Data structures & algorithms interview question — Apexed