58 7/31/2017 9:14:49 PM


:

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