BINARY-INSERTION-SORT (A, n) [ A[1 . . n]
for j ← 2 to n
insert key A[j] into the (already sorted) sub-array A[1 .. j-1].
Use binary search to find the right position
Binary search with take Θ(log n) time. However, shifting the elements after insertion will still take Θ(n) time.
Complexity: Θ(n log n) comparisons Θ (n 2) swaps