700 7/27/2015 2:09:36 AM


:

Sequence <A1', A2', ...An'> of numbers

:

Permutation of numbers <A1',A2',...An'>

:

Insertion Sort(A1n) //Sorts A[1...n]

FOR j <-- 2 to n

DO key <-- A[j]

i<-- j-1

WHILE i>0 AND A[i]> key

DO A[i+1] <--> A[i]

A[i] <-- key

i <-- i-1

 

:
  • Depends on input
    • If input revers sorted running time will be more
    • If input is alreay sorted running time will be minimum
  • Depends of input size.
    • Fast for small input size
    • Slow for input size is very large
  • Depends on computer
    • relative speed (same system)
    • absolute speed (different system)
:

Scenario: When input is reverse sorted.

T(n) = Ө(n2)