When implementing Insertion Sort, a binary
search could be used to locate the position within the first i-1
records of the array into which record i should be
inserted. In this implementation, the worst case time will be:
\Theta(n^2)\Theta(n \log n)\Theta(n)\Theta(\log n)The position to insert could be found in
\Theta (\log i), but shifting the records to
makeroom for the insert will still require
\Theta(i) time