Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* Copyright (C) 1999-2005 Henry Cejtin, Matthew Fluet, Suresh |
2 | * Jagannathan, and Stephen Weeks. | |
3 | * | |
4 | * MLton is released under a BSD-style license. | |
5 | * See the file MLton-LICENSE for details. | |
6 | *) | |
7 | ||
8 | structure InsertionSort: INSERTION_SORT = | |
9 | struct | |
10 | ||
11 | open Array | |
12 | ||
13 | (* Based on page 108 of Programming Pearls, by Bentley. *) | |
14 | fun sort (a: 'a array, op <= : 'a * 'a -> bool): unit = | |
15 | let | |
16 | fun x i = sub (a, i) | |
17 | val _ = | |
18 | Int.for | |
19 | (1, Array.length a, fn i => | |
20 | let | |
21 | val _ = | |
22 | if true | |
23 | then () | |
24 | else | |
25 | Assert.assert ("InsertionSort.sort: 1", fn () => | |
26 | Array.isSortedRange (a, 0, i, op <=)) | |
27 | val t = x i | |
28 | fun sift (j: int) = | |
29 | (if true | |
30 | then () | |
31 | else | |
32 | Assert.assert | |
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)) | |
37 | ; if j > 0 | |
38 | then | |
39 | let | |
40 | val j' = j - 1 | |
41 | val z = x j' | |
42 | in | |
43 | if z <= t | |
44 | then j | |
45 | else (update (a, j, z) | |
46 | ; sift j') | |
47 | end | |
48 | else j) | |
49 | val _ = update (a, sift i, t) | |
50 | in () | |
51 | end) | |
52 | val _ = | |
53 | Assert.assert ("InsertionSort.sort: 3", fn () => isSorted (a, op <=)) | |
54 | in | |
55 | () | |
56 | end | |
57 | ||
58 | end |