Skip to interview prep
Apexed

248. Compare bubble, selection, insertion, shell, merge, quick, heap and tree sort: which are stable, in-place and adaptive, and what are their best and worst cases?

EasySorting

Technical
Show model answer

Bubble sort (with an early-exit flag) and insertion sort are stable, in place and adaptive: O(n) on sorted input, O(n²) worst. Insertion sort really runs in O(n + d) where d is the number of inversions, which is why it is the go-to for small or almost-sorted inputs. Selection sort is in place but not stable in its usual array form and always does about n²/2 comparisons, although it performs at most n − 1 swaps, which helps when writes are expensive.

Shell sort is in place, not stable, and its running time depends on the gap sequence (roughly O(n^1.25)–O(n^1.5) in practice, O(n log² n) for Pratt gaps). Merge sort is stable with a guaranteed O(n log n) but needs O(n) extra space for arrays. Quicksort is in place (O(log n) stack with care) and not stable; it averages O(n log n) with the best constants but degrades to O(n²) with bad pivots. Heap sort is in place, not stable and O(n log n) in every case, but has poor cache locality.

Tree sort inserts into a binary search tree and does an in-order walk: O(n log n) on average, O(n²) if the tree degenerates (for example, sorted input into an unbalanced BST), plus O(n) memory for nodes. Using a balanced tree makes it O(n log n) worst case, and it is stable if equal keys are inserted to the right.

What interviewers listen for

  • Stable: bubble, insertion, merge, tree (with care)
  • Guaranteed O(n log n): merge, heap
  • Adaptive: insertion, bubble, Timsort
Compare bubble, selection, insertion, shell, merge, quick, heap and tree sort: which are stable, in-place and adaptive, and what are their best and worst cases