Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$
You still need to shift $O(n)$ elements to make room for the newly inserted element even if you find the correct position in $O(\log n)$.