function insertion_sort(list):
  FOR (i=0; i < list.length; i +=1) DO
    FOR (j=i; j > 0; j -=1) DO
      k = j - 1
      IF list[j] < list[k] THEN
        swap(list[j], list[k])
      END IF
    END FOR
  END FOR