comparison/SML/qsort-800000.sml


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

fun quicksort nil = nil
  | quicksort (pivot :: rest) =
    let
        fun split(nil) = (nil,nil)
          | split(x :: xs) =
          let
            val (below, above) = split(xs)
          in
            if x < pivot then (x :: below, above) 
            else (below, x :: above)
          end;
          val (below, above) = split(rest)
    in
        quicksort below @ [pivot] @ quicksort above
    end;
    
    
(* mkRandList *)
local 
    val nextInt = Random.randRange(1,10000);
    val r = Random.rand(1,1);
in
  fun mkRandList 0 = []
    | mkRandList n = (nextInt r)::(mkRandList (n-1))
end;
    
quicksort (mkRandList 800000);