Complexity Comparison Interview Questions

Merge sort: Always O(n log n) , O(n) extra space, stable — pick when worst case matters or sorting a linked list.

Quick sort: Average O(n log n) , in-place, not stable, worst case O(n²) with bad pivot.

Heap sort: O(n log n) , in-place, not stable.

Insertion sort: O(n²) but fast on nearly sorted data, O(1) extra space.

Quicksort average O(n log n) extra space O(log n) , but worst O(n squared) on already sorted data with a bad pivot. Mergesort is always O(n log n) and needs O(n) extra memory, and it is stable. I would use mergesort for linked lists and when I need a worst-case guarantee or stability. I would use well-pivoted quicksort for arrays in practice. I would not say 'quicksort is always faster'. I would say it depends on worst-case, stability, and memory.

Mergesort and insertion sort are stable. Heap sort and a naive quicksort are not. Stability matters when I sort by last name then want to keep the previous order by first name — two-key sorts. If I only have integers and no satellite data, stability may not matter. I mention that so I do not sound like I memorized a blog table.

Heapsort is O(n log n) worst case and O(1) extra array space, not stable. I would use it when I cannot afford mergesort's O(n) buffer and I cannot risk quicksort's worst case. In interviews it also explains why a heap exists. I would not pick heapsort for nearly sorted data — insertion sort is better then. I would not pick it when I need stable order.

Comparison sorts cannot beat O(n log n) in the worst case. Counting sort, radix sort, and bucket sort can be linear when the keys are integers in a small range. I would use counting sort for grades 0 to 100, not for arbitrary 64-bit ids. I would say the model matters: comparison versus integer keys. That sentence scores better than 'radix is O(n) so always use it'.