269. Does using binary search inside insertion sort make it O(n log n)?
MediumSorting
Technical
Show model answer
Binary search reduces the comparisons needed to find each insertion point to O(log i), so total comparisons drop to O(n log n). However, inserting still shifts every larger element one slot right, and those moves remain O(n²) in the worst case, so the overall running time is still O(n²).
It is worthwhile when comparisons are expensive relative to moves (for example, comparing long strings with cheap pointer moves). To keep the sort stable, search for the position after the last element equal to the new key (an upper bound search).