Input:

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

Output:

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

Pseudocode:

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

 

Running Time:
  • Depends on input
    • If input reverse sorted running time will be more
    • If input is already sorted running time will be minimum
  • Depends on 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)
Worst Case:

Scenario: When the input is reverse sorted.

T(n) = Ө(n2)