We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \log n)?$
Why isn't selection sort O(n log n)?
algorithms;algorithm analysis;sorting