Insertion sort

//input array A index starts at 1
function InsertionSort(A) {
    for (p = 2 to A.length) {
      key = A[p]
      i = p-1
      while (i > 0 && A[i] > key) {
        A[i+1] = A[i]
        i--
      }
      A[i+1] = key
    }
}