Sorting Algorithms

The sorting problem is as following:
Take a bunch of numbers, put them in order.

Input: We have a sequence <a1, a2, a3, ......, an>of number

.

Output: A permutation (rearrangement) <a1', a2', a3', ....., an'> of those numbers.

such that: a1' <= a2' <= ... <= an'

Psudo code of Insertion-Sort :

Insertion-Sort(A,n) //sort 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] 
                    i  <-- i - 1
                A[i+1] <-- key