open Array; (* swap exchanges A[i] with A[j] *) fun swap(A,i,j) = let val temp = sub(A,i) in (update(A,i,sub(A,j)); update(A,j,temp)) end; (* insert(A,i) pushes A[i] left until it finds an array element smaller than it. i.e., insert(A,i) inserts A[i] into its proper place in a sorted array A[0]...A[i-1] *) fun insert(A,0) = () | insert(A,i) = if sub(A,i-1) >= sub(A,i) then (swap(A,i-1,i); insert(A,i-1)) else (); (* isort1(A,i,n) inserts A[i]...A[n-1] into the sorted array A[0]...A[i-1] *) fun isort1(A,i,n) = if i>=n then () else (insert(A,i); isort1(A,i+1,n)); (* An insertion-sort function *) fun isort(A,n) = isort1(A,1,n);