1 (* Copyright (C
) 1999-2005 Henry Cejtin
, Matthew Fluet
, Suresh
2 * Jagannathan
, and Stephen Weeks
.
4 * MLton is released under a BSD
-style license
.
5 * See the file MLton
-LICENSE for details
.
8 structure InsertionSort
: INSERTION_SORT
=
13 (* Based on page
108 of Programming Pearls
, by Bentley
. *)
14 fun sort (a
: 'a array
, op <= : 'a
* 'a
-> bool): unit
=
19 (1, Array
.length a
, fn i
=>
25 Assert
.assert ("InsertionSort.sort: 1", fn () =>
26 Array
.isSortedRange (a
, 0, i
, op <=))
33 ("InsertionSort.sort: 2", fn () =>
34 Array
.isSortedRange (a
, 0, j
, op <=)
35 andalso Array
.isSortedRange (a
, j
+ 1, i
+ 1, op <=)
36 andalso Int.forall (j
+ 1, i
+ 1, fn k
=> t
<= x k
))
45 else (update (a
, j
, z
)
49 val _
= update (a
, sift i
, t
)
53 Assert
.assert ("InsertionSort.sort: 3", fn () => isSorted (a
, op <=))