基数ソート

radix_sort.ml

let radix_sort : int list -> int list = fun ns ->
  let ns =
    Array.fold_left (fun ns i ->
      let l, r = List.partition (fun n -> n land (1 lsl i) = 0) ns in
      l @ r) ns @@ Array.init 62 @@ fun i -> i in
  let l, r = List.partition (fun n -> n land (1 lsl 62) = 0) ns in
  r @ l;;

Random.self_init ();;
let true =
  List.for_all (fun ns -> radix_sort ns = List.sort compare ns) @@
    Array.to_list @@
      Array.init 100 @@ fun _ ->
        Array.to_list @@ Array.init 1000 @@ fun _ ->
          Random.bits () * if Random.bool () then -1 else 1;;

let measure f =
  let start = Sys.time () in
  f ();
  Sys.time () -. start;;

let l =
  Array.to_list @@
    Array.init 100000 @@ fun _ -> 
      Random.bits () * if Random.bool () then -1 else 1;;

measure @@ fun () -> ignore @@ radix_sort l;;
measure @@ fun () -> ignore @@ List.sort compare l;;