Problem Statement

An O(n2) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part. Although insertion sort is an O(n2) algorithm, its simplicity, low overhead, good locality of reference and efficiency make it a good choice in two cases:

The algorithm is as follows (from wikipedia): Writing the algorithm for integers will suffice.

Let's start with the solution:

PROGRAM INSERTION_SORT

DIM A[9]

PROCEDURE INSERTION_SORT(A[])
    LOCAL I,J
    FOR I=0 TO UBOUND(A,1) DO
        V=A[I]
        J=I-1
        WHILE J>=0 DO
          IF A[J]>V THEN
            A[J+1]=A[J]
            J=J-1
           ELSE
            EXIT
          END IF
        END WHILE
        A[J+1]=V
    END FOR
END PROCEDURE

BEGIN
  A[]=(4,65,2,-31,0,99,2,83,782,1)
  FOR I%=0 TO UBOUND(A,1) DO
     PRINT(A[I%];)
  END FOR
  PRINT
  INSERTION_SORT(A[])
  FOR I%=0 TO UBOUND(A,1) DO
     PRINT(A[I%];)
  END FOR
  PRINT
END PROGRAM