1(* Test bench for sorting algorithms. *) 2 3 4(* 5 ocamlopt -noassert sorts.ml -cclib -lunix 6*) 7 8open Printf;; 9 10(* 11 Criteria: 12 0. stack overhead: at most log n. 13 1. stable or not. 14 2. space overhead. 15 3. speed. 16*) 17 18(************************************************************************) 19(* auxiliary functions *) 20 21let rec exp2 n = if n <= 0 then 1 else 2 * exp2 (n-1);; 22let id x = x;; 23let postl x y = Array.of_list y;; 24let posta x y = x;; 25 26let mkconst n = Array.make n 0;; 27let chkconst _ n a = (a = mkconst n);; 28 29let mksorted n = 30 let a = Array.make n 0 in 31 for i = 0 to n - 1 do 32 a.(i) <- i; 33 done; 34 a 35;; 36let chksorted _ n a = (a = mksorted n);; 37 38let mkrev n = 39 let a = Array.make n 0 in 40 for i = 0 to n - 1 do 41 a.(i) <- n - 1 - i; 42 done; 43 a 44;; 45let chkrev _ n a = (a = mksorted n);; 46 47let seed = ref 0;; 48let random_reinit () = Random.init !seed;; 49 50let random_get_state () = 51 let a = Array.make 55 0 in 52 for i = 0 to 54 do a.(i) <- Random.bits (); done; 53 Random.full_init a; 54 a 55;; 56let random_set_state a = Random.full_init a;; 57 58let chkgen mke cmp rstate n a = 59 let marks = Array.make n (-1) in 60 let skipmarks l = 61 if marks.(l) = -1 then l else begin 62 let m = ref marks.(l) in 63 while marks.(!m) <> -1 do incr m; done; 64 marks.(l) <- !m; 65 !m 66 end 67 in 68 let linear e l = 69 let l = skipmarks l in 70 let rec loop l = 71 if cmp a.(l) e > 0 then raise Exit 72 else if e = a.(l) then marks.(l) <- l+1 73 else loop (l+1) 74 in loop l 75 in 76 let rec dicho e l r = 77 if l = r then linear e l 78 else begin 79 assert (l < r); 80 let m = (l + r) / 2 in 81 if cmp a.(m) e >= 0 then dicho e l m else dicho e (m + 1) r 82 end 83 in 84 try 85 for i = 0 to n-2 do if cmp a.(i) a.(i+1) > 0 then raise Exit; done; 86 random_set_state rstate; 87 for i = 0 to n-1 do dicho (mke i) 0 (Array.length a - 1); done; 88 true 89 with Exit | Invalid_argument _ -> false; 90;; 91 92let mkrand_dup n = 93 let a = Array.make n 0 in 94 for i = 0 to (n-1) do a.(i) <- Random.int n; done; 95 a 96;; 97 98let chkrand_dup rstate n a = 99 chkgen (fun i -> Random.int n) compare rstate n a 100;; 101 102let mkrand_nodup n = 103 let a = Array.make n 0 in 104 for i = 0 to (n-1) do a.(i) <- Random.bits (); done; 105 a 106;; 107 108let chkrand_nodup rstate n a = 109 chkgen (fun i -> Random.bits ()) compare rstate n a 110;; 111 112let mkfloats n = 113 let a = Array.make n 0.0 in 114 for i = 0 to (n-1) do a.(i) <- Random.float 1.0; done; 115 a 116;; 117 118let chkfloats rstate n a = 119 chkgen (fun i -> Random.float 1.0) compare rstate n a 120;; 121 122type record = { 123 s1 : bytes; 124 s2 : bytes; 125 i1 : int; 126 i2 : int; 127};; 128 129let rand_string () = 130 let len = Random.int 10 in 131 let s = String.create len in 132 for i = 0 to len-1 do 133 s.[i] <- Char.chr (Random.int 256); 134 done; 135 s 136;; 137 138let mkrec1 b i = { 139 s1 = rand_string (); 140 s2 = rand_string (); 141 i1 = Random.int b; 142 i2 = i; 143};; 144 145let mkrecs b n = Array.init n (mkrec1 b);; 146 147let mkrec1_rev b i = { 148 s1 = rand_string (); 149 s2 = rand_string (); 150 i1 = - i; 151 i2 = i; 152};; 153 154let mkrecs_rev n = Array.init n (mkrec1_rev 0);; 155 156let cmpstr r1 r2 = 157 let c1 = compare r1.s1 r2.s1 in 158 if c1 = 0 then compare r1.s2 r2.s2 else c1 159;; 160let lestr r1 r2 = 161 let c1 = compare r1.s1 r2.s1 in 162 if c1 = 0 then r1.s2 <= r2.s2 else (c1 < 0) 163;; 164let chkstr b rstate n a = chkgen (mkrec1 b) cmpstr rstate n a;; 165 166let cmpint r1 r2 = compare r1.i1 r2.i1;; 167let leint r1 r2 = r1.i1 <= r2.i1;; 168let chkint b rstate n a = chkgen (mkrec1 b) cmpint rstate n a;; 169 170let cmplex r1 r2 = 171 let c1 = compare r1.i1 r2.i1 in 172 if c1 = 0 then compare r1.i2 r2.i2 else c1 173;; 174let lelex r1 r2 = 175 let c1 = compare r1.i1 r2.i1 in 176 if c1 = 0 then r1.i2 <= r2.i2 else (c1 < 0) 177;; 178let chklex b rstate n a = chkgen (mkrec1 b) cmplex rstate n a;; 179 180(************************************************************************) 181 182let lens = [ 183 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 28; 184 100; 127; 128; 129; 193; 506; 185 1000; 1025; 1535; 2323; 186];; 187 188type ('a, 'b, 'c, 'd) aux = { 189 prepf : ('a -> 'a -> int) -> ('a -> 'a -> bool) -> 'b; 190 prepd : 'a array -> 'c; 191 postd : 'a array -> 'd -> 'a array; 192};; 193 194let ll = { prepf = (fun x y -> y); prepd = Array.to_list; postd = postl };; 195let lc = { prepf = (fun x y -> x); prepd = Array.to_list; postd = postl };; 196let al = { prepf = (fun x y -> y); prepd = id; postd = posta };; 197let ac = { prepf = (fun x y -> x); prepd = id; postd = posta };; 198 199type 'a outcome = Value of 'a | Exception of exn;; 200 201let numfailed = ref 0;; 202 203let test1 name f prepdata postdata cmp desc mk chk = 204 random_reinit (); 205 printf " %s with %s" name desc; 206 let i = ref 0 in 207 List.iter (fun n -> 208 if !i = 0 then printf "\n "; incr i; if !i > 11 then i := 0; 209 printf "%5d" n; flush stdout; 210 let rstate = random_get_state () in 211 let a = mk n in 212 let input = prepdata a in 213 let output = try Value (f cmp input) with e -> Exception e in 214 printf "."; flush stdout; 215 begin match output with 216 | Value v -> 217 if not (chk rstate n (postdata a v)) 218 then (incr numfailed; printf "\n*** FAIL\n") 219 | Exception e -> 220 incr numfailed; printf "\n*** %s\n" (Printexc.to_string e) 221 end; 222 flush stdout; 223 ) lens; 224 printf "\n"; 225;; 226 227let test name stable f1 f2 aux1 aux2 = 228 printf "Testing %s...\n" name; 229 let t a b c d = test1 name f1 aux1.prepd aux1.postd a b c d in 230 let cmp = aux1.prepf compare (<=) in 231 t cmp "constant ints" mkconst chkconst; 232 t cmp "sorted ints" mksorted chksorted; 233 t cmp "reverse-sorted ints" mkrev chkrev; 234 t cmp "random ints (many dups)" mkrand_dup chkrand_dup; 235 t cmp "random ints (few dups)" mkrand_nodup chkrand_nodup; 236(* 237 let t a b c d = test1 name f3 aux3.prepd aux3.postd a b c d in 238 t cmp "random floats" mkfloats chkfloats; 239*) 240 let t a b c d = test1 name f2 aux2.prepd aux2.postd a b c d in 241 let cmp = aux2.prepf cmpstr lestr in 242 t cmp "records (str)" (mkrecs 1) (chkstr 1); 243 let cmp = aux2.prepf cmpint leint in 244 List.iter (fun m -> t cmp (sprintf "records (int[%d])" m) (mkrecs m) 245 (chkint m) 246 ) [1; 10; 100; 1000]; 247 if stable then 248 List.iter (fun m -> t cmp (sprintf "records (int[%d]) [stable]" m) 249 (mkrecs m) (chklex m) 250 ) [1; 10; 100; 1000]; 251;; 252 253(************************************************************************) 254 255(* Warning: rpt_timer cannot be used for the array sorts because 256 the sorting functions have effects. 257*) 258 259let rpt_timer1 repeat f x = 260 Gc.compact (); 261 ignore (f x); 262 let st = Sys.time () in 263 for i = 1 to repeat do ignore (f x); done; 264 let en = Sys.time () in 265 en -. st 266;; 267 268let rpt_timer f x = 269 let repeat = ref 1 in 270 let t = ref (rpt_timer1 !repeat f x) in 271 while !t < 0.2 do 272 repeat := 10 * !repeat; 273 t := rpt_timer1 !repeat f x; 274 done; 275 if !t < 2.0 then begin 276 repeat := (int_of_float (10. *. (float !repeat) /. !t) + 1); 277 t := rpt_timer1 !repeat f x; 278 end; 279 !t /. (float !repeat) 280;; 281 282let timer f x = 283 let st = Sys.time () in 284 ignore (f x); 285 let en = Sys.time () in 286 (en -. st) 287;; 288 289let table1 limit f mkarg = 290 printf " %10s %9s %9s %9s %9s %9s\n" "n" "t1" "t2" "t3" "t4" "t5"; 291 let sz = ref 49151 in 292 while !sz < int_of_float (2. ** float limit) do 293 begin try 294 printf " %10d " !sz; flush stdout; 295 for i = 0 to 4 do 296 let arg = mkarg !sz in 297 let t = timer f arg in 298 printf " %.2e " t; flush stdout; 299 done; 300 printf "\n"; 301 with e -> printf "*** %s\n" (Printexc.to_string e); 302 end; 303 flush stdout; 304 sz := 2 * !sz + 1; 305 done; 306;; 307 308let table2 limit f mkarg = 309 printf " %10s %9s %9s %9s %9s %9s\n" 310 " n" "t" "t/n" "t/nlogn" "t/nlog^2n" "t/n^2"; 311 let sz = ref 49151 in 312 while float !sz < 2. ** float limit do 313 begin try 314 printf " %10d " !sz; flush stdout; 315 Gc.compact (); 316 let arg = mkarg !sz in 317 let t = timer f arg in 318 let n = float !sz in 319 let logn = log (float !sz) /. log 2. in 320 printf "%.2e %.2e %.2e %.2e %.2e\n" 321 t (t/.n) (t/.n/.logn) (t/.n/.logn/.logn) (t/.n/.n); 322 with e -> printf "*** %s\n" (Printexc.to_string e); 323 end; 324 flush stdout; 325 sz := 2 * !sz + 1; 326 done; 327;; 328 329let table3 limit f mkarg = 330 printf " %10s %9s %9s %9s %9s %9s\n" "n" "t1" "t2" "t3" "t4" "t5"; 331 let sz = ref 2 in 332 while float !sz < 2. ** float limit do 333 begin try 334 printf " %10d " !sz; flush stdout; 335 for i = 0 to 4 do 336 let arg = mkarg !sz in 337 let t = rpt_timer f arg in 338 printf " %.2e " t; flush stdout; 339 done; 340 printf "\n"; 341 with e -> printf "*** %s\n" (Printexc.to_string e); 342 end; 343 flush stdout; 344 sz := 2 * !sz + 1; 345 done; 346;; 347 348(************************************************************************) 349 350(* benchmarks: 351 1a. random records, sorted with two keys 352 1b. random integers 353 1c. random floats 354 355 2a. integers, constant 356 2b. integers, already sorted 357 2c. integers, reverse sorted 358 359 only for short lists: 360 3a. random records, sorted with two keys 361 3b. random integers 362 3c. random floats 363*) 364let bench1a limit name f aux = 365 366 (* Don't do benchmarks with assertions enabled. *) 367 assert (not true); 368 369 random_reinit (); 370 371 printf "\n%s with random records [10]:\n" name; 372 let cmp = aux.prepf cmplex lelex in 373 table1 limit (f cmp) (fun n -> aux.prepd (mkrecs 10 n)); 374;; 375 376let bench1b limit name f aux = 377 378 (* Don't do benchmarks with assertions enabled. *) 379 assert (not true); 380 381 random_reinit (); 382 383 printf "\n%s with random integers:\n" name; 384 let cmp = aux.prepf (-) (<=) in 385 table1 limit (f cmp) (fun n -> aux.prepd (mkrand_nodup n)); 386;; 387 388let bench1c limit name f aux = 389 390 (* Don't do benchmarks with assertions enabled. *) 391 assert (not true); 392 393 random_reinit (); 394 395 printf "\n%s with random floats:\n" name; 396 let cmp = aux.prepf compare (<=) in 397 table1 limit (f cmp) (fun n -> aux.prepd (mkfloats n)); 398;; 399 400let bench2 limit name f aux = 401 402 (* Don't do benchmarks with assertions enabled. *) 403 assert (not true); 404 405 printf "\n%s with constant integers:\n" name; 406 let cmp = aux.prepf compare (<=) in 407 table2 limit (f cmp) (fun n -> aux.prepd (mkconst n)); 408 409 printf "\n%s with sorted integers:\n" name; 410 let cmp = aux.prepf compare (<=) in 411 table2 limit (f cmp) (fun n -> aux.prepd (mksorted n)); 412 413 printf "\n%s with reverse-sorted integers:\n" name; 414 let cmp = aux.prepf compare (<=) in 415 table2 limit (f cmp) (fun n -> aux.prepd (mkrev n)); 416;; 417 418let bench3a limit name f aux = 419 420 (* Don't do benchmarks with assertions enabled. *) 421 assert (not true); 422 423 random_reinit (); 424 425 printf "\n%s with random records [10]:\n" name; 426 let cmp = aux.prepf cmplex lelex in 427 table3 limit (f cmp) (fun n -> aux.prepd (mkrecs 10 n)); 428;; 429 430let bench3b limit name f aux = 431 432 (* Don't do benchmarks with assertions enabled. *) 433 assert (not true); 434 435 random_reinit (); 436 437 printf "\n%s with random integers:\n" name; 438 let cmp = aux.prepf (-) (<=) in 439 table3 limit (f cmp) (fun n -> aux.prepd (mkrand_nodup n)); 440;; 441 442let bench3c limit name f aux = 443 444 (* Don't do benchmarks with assertions enabled. *) 445 assert (not true); 446 447 random_reinit (); 448 449 printf "\n%s with random floats:\n" name; 450 let cmp = aux.prepf compare (<=) in 451 table3 limit (f cmp) (fun n -> aux.prepd (mkfloats n)); 452;; 453 454(************************************************************************) 455(* merge sort on lists *) 456 457(* FIXME to do: cutoff 458 to do: cascade pattern-matchings (delete pairs) 459 to do: intermediary closure for merge 460*) 461let (@@) = List.rev_append;; 462 463let lmerge_1a cmp l = 464 let rec init accu = function 465 | [] -> accu 466 | e::rest -> init ([e] :: accu) rest 467 in 468 let rec merge rest accu2 accu l1 l2 = (* l1,l2,rest are forward; 469 accu,accu2 are rev *) 470 match l1, l2 with 471 | [] , _ -> mergepairs ((l2 @@ accu)::accu2) rest 472 | _ , [] -> mergepairs ((l1 @@ accu)::accu2) rest 473 | h1::t1, h2::t2 -> if cmp h1 h2 <= 0 474 then merge rest accu2 (h1::accu) t1 l2 475 else merge rest accu2 (h2::accu) l1 t2 476 and merge_rev rest accu2 accu l1 l2 = (* accu, accu2 are forward; 477 l1,l2,rest are rev *) 478 match l1, l2 with 479 | [] , _ -> mergepairs_rev ((l2 @@ accu)::accu2) rest 480 | _ , [] -> mergepairs_rev ((l1 @@ accu)::accu2) rest 481 | h1::t1, h2::t2 -> if cmp h2 h1 <= 0 482 then merge_rev rest accu2 (h1::accu) t1 l2 483 else merge_rev rest accu2 (h2::accu) l1 t2 484 and mergepairs accu = function (* accu is rev, arg is forward *) 485 | [] -> mergeall_rev accu 486 | [l] -> mergeall_rev ((List.rev l)::accu) 487 | l1::l2::rest -> merge rest accu [] l1 l2 488 and mergepairs_rev accu = function (* accu is forward, arg is rev *) 489 | [] -> mergeall accu 490 | [l] -> mergeall ((List.rev l)::accu) 491 | l1::l2::rest -> merge_rev rest accu [] l1 l2 492 and mergeall = function (* arg is forward *) 493 | [] -> [] 494 | [l] -> l 495 | llist -> mergepairs [] llist 496 and mergeall_rev = function (* arg is rev *) 497 | [] -> [] 498 | [l] -> List.rev l 499 | llist -> mergepairs_rev [] llist 500 in 501 mergeall_rev (init [] l) 502;; 503 504let lmerge_1b cmp l = 505 let rec init accu = function 506 | [] -> accu 507 | [e] -> [e] :: accu 508 | e1::e2::rest -> 509 init ((if cmp e1 e2 <= 0 then [e2;e1] else [e1;e2])::accu) rest 510 in 511 let rec merge rest accu2 accu l1 l2 = (* l1,l2,rest are forward; 512 accu,accu2 are rev *) 513 match l1, l2 with 514 | [] , _ -> mergepairs ((l2 @@ accu)::accu2) rest 515 | _ , [] -> mergepairs ((l1 @@ accu)::accu2) rest 516 | h1::t1, h2::t2 -> if cmp h1 h2 <= 0 517 then merge rest accu2 (h1::accu) t1 l2 518 else merge rest accu2 (h2::accu) l1 t2 519 and merge_rev rest accu2 accu l1 l2 = (* accu, accu2 are forward; 520 l1,l2,rest are rev *) 521 match l1, l2 with 522 | [] , _ -> mergepairs_rev ((l2 @@ accu)::accu2) rest 523 | _ , [] -> mergepairs_rev ((l1 @@ accu)::accu2) rest 524 | h1::t1, h2::t2 -> if cmp h2 h1 <= 0 525 then merge_rev rest accu2 (h1::accu) t1 l2 526 else merge_rev rest accu2 (h2::accu) l1 t2 527 and mergepairs accu = function (* accu is rev, arg is forward *) 528 | [] -> mergeall_rev accu 529 | [l] -> mergeall_rev ((List.rev l)::accu) 530 | l1::l2::rest -> merge rest accu [] l1 l2 531 and mergepairs_rev accu = function (* accu is forward, arg is rev *) 532 | [] -> mergeall accu 533 | [l] -> mergeall ((List.rev l)::accu) 534 | l1::l2::rest -> merge_rev rest accu [] l1 l2 535 and mergeall = function (* arg is forward *) 536 | [] -> [] 537 | [l] -> l 538 | llist -> mergepairs [] llist 539 and mergeall_rev = function (* arg is rev *) 540 | [] -> [] 541 | [l] -> List.rev l 542 | llist -> mergepairs_rev [] llist 543 in 544 mergeall_rev (init [] l) 545;; 546 547let lmerge_1c cmp l = 548 let rec init accu = function 549 | [] -> accu 550 | [e] -> [e] :: accu 551 | e1::e2::rest -> 552 init ((if cmp e1 e2 <= 0 then [e2;e1] else [e1;e2])::accu) rest 553 in 554 let rec merge rest accu2 accu l1 l2 = (* l1,l2,rest are forward; 555 accu,accu2 are rev *) 556 match l1 with 557 | [] -> mergepairs ((l2 @@ accu)::accu2) rest 558 | h1::t1 -> 559 match l2 with 560 | [] -> mergepairs ((l1 @@ accu)::accu2) rest 561 | h2::t2 -> if cmp h1 h2 <= 0 562 then merge rest accu2 (h1::accu) t1 l2 563 else merge rest accu2 (h2::accu) l1 t2 564 and merge_rev rest accu2 accu l1 l2 = (* accu, accu2 are forward; 565 l1,l2,rest are rev *) 566 match l1 with 567 | [] -> mergepairs_rev ((l2 @@ accu)::accu2) rest 568 | h1::t1 -> 569 match l2 with 570 | [] -> mergepairs_rev ((l1 @@ accu)::accu2) rest 571 | h2::t2 -> if cmp h2 h1 <= 0 572 then merge_rev rest accu2 (h1::accu) t1 l2 573 else merge_rev rest accu2 (h2::accu) l1 t2 574 and mergepairs accu = function (* accu is rev, arg is forward *) 575 | [] -> mergeall_rev accu 576 | [l] -> mergeall_rev ((List.rev l)::accu) 577 | l1::l2::rest -> merge rest accu [] l1 l2 578 and mergepairs_rev accu = function (* accu is forward, arg is rev *) 579 | [] -> mergeall accu 580 | [l] -> mergeall ((List.rev l)::accu) 581 | l1::l2::rest -> merge_rev rest accu [] l1 l2 582 and mergeall = function (* arg is forward *) 583 | [] -> [] 584 | [l] -> l 585 | llist -> mergepairs [] llist 586 and mergeall_rev = function (* arg is rev *) 587 | [] -> [] 588 | [l] -> List.rev l 589 | llist -> mergepairs_rev [] llist 590 in 591 mergeall_rev (init [] l) 592;; 593 594let lmerge_1d cmp l = 595 let rec init accu = function 596 | [] -> accu 597 | [e] -> [e] :: accu 598 | e1::e2::rest -> 599 init ((if cmp e1 e2 <= 0 then [e2;e1] else [e1;e2])::accu) rest 600 in 601 let rec merge rest accu2 accu l1 l2 = (* l1,l2,rest are forward; 602 accu,accu2 are rev *) 603 let merge_rest_accu2 accu l1 l2 = 604 match l1 with 605 | [] -> mergepairs ((l2 @@ accu)::accu2) rest 606 | h1::t1 -> 607 match l2 with 608 | [] -> mergepairs ((l1 @@ accu)::accu2) rest 609 | h2::t2 -> if cmp h1 h2 <= 0 610 then merge rest accu2 (h1::accu) t1 l2 611 else merge rest accu2 (h2::accu) l1 t2 612 in merge_rest_accu2 accu l1 l2 613 and merge_rev rest accu2 accu l1 l2 = (* accu, accu2 are forward; 614 l1,l2,rest are rev *) 615 let merge_rev_rest_accu2 accu l1 l2 = 616 match l1 with 617 | [] -> mergepairs_rev ((l2 @@ accu)::accu2) rest 618 | h1::t1 -> 619 match l2 with 620 | [] -> mergepairs_rev ((l1 @@ accu)::accu2) rest 621 | h2::t2 -> if cmp h2 h1 <= 0 622 then merge_rev rest accu2 (h1::accu) t1 l2 623 else merge_rev rest accu2 (h2::accu) l1 t2 624 in merge_rev_rest_accu2 accu l1 l2 625 and mergepairs accu = function (* accu is rev, arg is forward *) 626 | [] -> mergeall_rev accu 627 | [l] -> mergeall_rev ((List.rev l)::accu) 628 | l1::l2::rest -> merge rest accu [] l1 l2 629 and mergepairs_rev accu = function (* accu is forward, arg is rev *) 630 | [] -> mergeall accu 631 | [l] -> mergeall ((List.rev l)::accu) 632 | l1::l2::rest -> merge_rev rest accu [] l1 l2 633 and mergeall = function (* arg is forward *) 634 | [] -> [] 635 | [l] -> l 636 | llist -> mergepairs [] llist 637 and mergeall_rev = function (* arg is rev *) 638 | [] -> [] 639 | [l] -> List.rev l 640 | llist -> mergepairs_rev [] llist 641 in 642 mergeall_rev (init [] l) 643;; 644 645(************************************************************************) 646(* merge sort on lists, user-contributed (NOT STABLE) *) 647 648(* BEGIN code contributed by Yann Coscoy *) 649 650 let rec rev_merge_append order l1 l2 acc = 651 match l1 with 652 [] -> List.rev_append l2 acc 653 | h1 :: t1 -> 654 match l2 with 655 [] -> List.rev_append l1 acc 656 | h2 :: t2 -> 657 if order h1 h2 658 then rev_merge_append order t1 l2 (h1::acc) 659 else rev_merge_append order l1 t2 (h2::acc) 660 661 let rev_merge order l1 l2 = rev_merge_append order l1 l2 [] 662 663 let rec rev_merge_append' order l1 l2 acc = 664 match l1 with 665 | [] -> List.rev_append l2 acc 666 | h1 :: t1 -> 667 match l2 with 668 | [] -> List.rev_append l1 acc 669 | h2 :: t2 -> 670 if order h2 h1 671 then rev_merge_append' order t1 l2 (h1::acc) 672 else rev_merge_append' order l1 t2 (h2::acc) 673 674 let rev_merge' order l1 l2 = rev_merge_append' order l1 l2 [] 675 676 let lmerge_3 order l = 677 let rec initlist l acc = match l with 678 | e1::e2::rest -> 679 initlist rest 680 ((if order e1 e2 then [e1;e2] else [e2;e1])::acc) 681 | [e] -> [e]::acc 682 | [] -> acc 683 in 684 let rec merge2 ll acc = match ll with 685 | [] -> acc 686 | [l] -> [List.rev l]@acc 687 | l1::l2::rest -> 688 merge2 rest (rev_merge order l1 l2::acc) 689 in 690 let rec merge2' ll acc = match ll with 691 | [] -> acc 692 | [l] -> [List.rev l]@acc 693 | l1::l2::rest -> 694 merge2' rest (rev_merge' order l1 l2::acc) 695 in 696 let rec mergeall rev = function 697 | [] -> [] 698 | [l] -> if rev then List.rev l else l 699 | llist -> 700 mergeall 701 (not rev) ((if rev then merge2' else merge2) llist []) 702 in 703 mergeall false (initlist l []) 704 705(* END code contributed by Yann Coscoy *) 706 707(************************************************************************) 708(* merge sort on short lists, Francois Pottier *) 709 710(* BEGIN code contributed by Francois Pottier *) 711 712 (* [chop k l] returns the list [l] deprived of its [k] first 713 elements. The length of the list [l] must be [k] at least. *) 714 715 let rec chop k l = 716 match k, l with 717 | 0, _ -> l 718 | _, x :: l -> chop (k-1) l 719 | _, _ -> assert false 720 ;; 721 722 let rec merge order l1 l2 = 723 match l1 with 724 [] -> l2 725 | h1 :: t1 -> 726 match l2 with 727 [] -> l1 728 | h2 :: t2 -> 729 if order h1 h2 730 then h1 :: merge order t1 l2 731 else h2 :: merge order l1 t2 732 ;; 733 734 let rec lmerge_4a order l = 735 match l with 736 | [] 737 | [ _ ] -> l 738 | _ -> 739 let rec sort k l = (* k > 1 *) 740 match k, l with 741 | 2, x1 :: x2 :: _ -> 742 if order x1 x2 then [ x1; x2 ] else [ x2; x1 ] 743 | 3, x1 :: x2 :: x3 :: _ -> 744 if order x1 x2 then 745 if order x2 x3 then 746 [ x1 ; x2 ; x3 ] 747 else 748 if order x1 x3 then [ x1 ; x3 ; x2 ] else [ x3; x1; x2 ] 749 else 750 if order x1 x3 then 751 [ x2; x1; x3 ] 752 else 753 if order x2 x3 then [ x2; x3; x1 ] else [ x3; x2; x1 ] 754 | _, _ -> 755 let k1 = k / 2 in 756 let k2 = k - k1 in 757 merge order (sort k1 l) (sort k2 (chop k1 l)) 758 in 759 sort (List.length l) l 760 ;; 761(* END code contributed by Francois Pottier *) 762 763(************************************************************************) 764(* merge sort on short lists, Francois Pottier, 765 adapted to new-style interface *) 766 767(* BEGIN code contributed by Francois Pottier *) 768 769 (* [chop k l] returns the list [l] deprived of its [k] first 770 elements. The length of the list [l] must be [k] at least. *) 771 772 let rec chop k l = 773 match k, l with 774 | 0, _ -> l 775 | _, x :: l -> chop (k-1) l 776 | _, _ -> assert false 777 ;; 778 779 let rec merge order l1 l2 = 780 match l1 with 781 [] -> l2 782 | h1 :: t1 -> 783 match l2 with 784 [] -> l1 785 | h2 :: t2 -> 786 if order h1 h2 <= 0 787 then h1 :: merge order t1 l2 788 else h2 :: merge order l1 t2 789 ;; 790 791 let rec lmerge_4b order l = 792 match l with 793 | [] 794 | [ _ ] -> l 795 | _ -> 796 let rec sort k l = (* k > 1 *) 797 match k, l with 798 | 2, x1 :: x2 :: _ -> 799 if order x1 x2 <= 0 then [ x1; x2 ] else [ x2; x1 ] 800 | 3, x1 :: x2 :: x3 :: _ -> 801 if order x1 x2 <= 0 then 802 if order x2 x3 <= 0 then 803 [ x1 ; x2 ; x3 ] 804 else 805 if order x1 x3 <= 0 then [ x1 ; x3 ; x2 ] else [ x3; x1; x2 ] 806 else 807 if order x1 x3 <= 0 then 808 [ x2; x1; x3 ] 809 else 810 if order x2 x3 <= 0 then [ x2; x3; x1 ] else [ x3; x2; x1 ] 811 | _, _ -> 812 let k1 = k / 2 in 813 let k2 = k - k1 in 814 merge order (sort k1 l) (sort k2 (chop k1 l)) 815 in 816 sort (List.length l) l 817 ;; 818(* END code contributed by Francois Pottier *) 819 820(************************************************************************) 821(* merge sort on short lists a la Pottier, modified merge *) 822 823let rec chop k l = 824 if k = 0 then l else begin 825 match l with 826 | x::t -> chop (k-1) t 827 | _ -> assert false 828 end 829;; 830 831let lmerge_4c cmp l = 832 let rec merge1 h1 t1 l2 = 833 match l2 with 834 | [] -> h1 :: t1 835 | h2 :: t2 -> 836 if cmp h1 h2 <= 0 837 then h1 :: (merge2 t1 h2 t2) 838 else h2 :: (merge1 h1 t1 t2) 839 and merge2 l1 h2 t2 = 840 match l1 with 841 | [] -> h2 :: t2 842 | h1 :: t1 -> 843 if cmp h1 h2 <= 0 844 then h1 :: (merge2 t1 h2 t2) 845 else h2 :: (merge1 h1 t1 t2) 846 in 847 let merge l1 = function 848 | [] -> l1 849 | h2 :: t2 -> merge2 l1 h2 t2 850 in 851 let rec sort n l = 852 match n, l with 853 | 2, x1 :: x2 :: _ -> 854 if cmp x1 x2 <= 0 then [x1; x2] else [x2; x1] 855 | 3, x1 :: x2 :: x3 :: _ -> 856 if cmp x1 x2 <= 0 then begin 857 if cmp x2 x3 <= 0 then [x1; x2; x3] 858 else if cmp x1 x3 <= 0 then [x1; x3; x2] 859 else [x3; x1; x2] 860 end else begin 861 if cmp x1 x3 <= 0 then [x2; x1; x3] 862 else if cmp x2 x3 <= 0 then [x2; x3; x1] 863 else [x3; x2; x1] 864 end 865 | n, l -> 866 let n1 = n asr 1 in 867 let n2 = n - n1 in 868 merge (sort n1 l) (sort n2 (chop n1 l)) 869 in 870 let len = List.length l in 871 if len < 2 then l else sort len l 872;; 873 874(************************************************************************) 875(* merge sort on short lists a la Pottier, logarithmic stack space *) 876 877let rec chop k l = 878 if k = 0 then l else begin 879 match l with 880 | x::t -> chop (k-1) t 881 | _ -> assert false 882 end 883;; 884 885let lmerge_4d cmp l = 886 let rec rev_merge l1 l2 accu = 887 match l1, l2 with 888 | [], l2 -> l2 @@ accu 889 | l1, [] -> l1 @@ accu 890 | h1::t1, h2::t2 -> 891 if cmp h1 h2 <= 0 892 then rev_merge t1 l2 (h1::accu) 893 else rev_merge l1 t2 (h2::accu) 894 in 895 let rec rev_merge_rev l1 l2 accu = 896 match l1, l2 with 897 | [], l2 -> l2 @@ accu 898 | l1, [] -> l1 @@ accu 899 | h1::t1, h2::t2 -> 900 if cmp h1 h2 > 0 901 then rev_merge_rev t1 l2 (h1::accu) 902 else rev_merge_rev l1 t2 (h2::accu) 903 in 904 let rec sort n l = 905 match n, l with 906 | 2, x1 :: x2 :: _ -> 907 if cmp x1 x2 <= 0 then [x1; x2] else [x2; x1] 908 | 3, x1 :: x2 :: x3 :: _ -> 909 if cmp x1 x2 <= 0 then begin 910 if cmp x2 x3 <= 0 then [x1; x2; x3] 911 else if cmp x1 x3 <= 0 then [x1; x3; x2] 912 else [x3; x1; x2] 913 end else begin 914 if cmp x1 x3 <= 0 then [x2; x1; x3] 915 else if cmp x2 x3 <= 0 then [x2; x3; x1] 916 else [x3; x2; x1] 917 end 918 | n, l -> 919 let n1 = n asr 1 in 920 let n2 = n - n1 in 921 rev_merge_rev (rev_sort n1 l) (rev_sort n2 (chop n1 l)) [] 922 and rev_sort n l = 923 match n, l with 924 | 2, x1 :: x2 :: _ -> 925 if cmp x1 x2 > 0 then [x1; x2] else [x2; x1] 926 | 3, x1 :: x2 :: x3 :: _ -> 927 if cmp x1 x2 > 0 then begin 928 if cmp x2 x3 > 0 then [x1; x2; x3] 929 else if cmp x1 x3 > 0 then [x1; x3; x2] 930 else [x3; x1; x2] 931 end else begin 932 if cmp x1 x3 > 0 then [x2; x1; x3] 933 else if cmp x2 x3 > 0 then [x2; x3; x1] 934 else [x3; x2; x1] 935 end 936 | n, l -> 937 let n1 = n asr 1 in 938 let n2 = n - n1 in 939 rev_merge (sort n1 l) (sort n2 (chop n1 l)) [] 940 in 941 let len = List.length l in 942 if len < 2 then l else sort len l 943;; 944 945 946(************************************************************************) 947(* merge sort on short lists a la Pottier, logarithmic stack space, 948 in place: input list is freed as the output is being computed. *) 949 950let rec chop k l = 951 if k = 0 then l else begin 952 match l with 953 | x::t -> chop (k-1) t 954 | _ -> assert false 955 end 956;; 957 958let lmerge_4e cmp l = 959 let rec rev_merge l1 l2 accu = 960 match l1, l2 with 961 | [], l2 -> l2 @@ accu 962 | l1, [] -> l1 @@ accu 963 | h1::t1, h2::t2 -> 964 if cmp h1 h2 <= 0 965 then rev_merge t1 l2 (h1::accu) 966 else rev_merge l1 t2 (h2::accu) 967 in 968 let rec rev_merge_rev l1 l2 accu = 969 match l1, l2 with 970 | [], l2 -> l2 @@ accu 971 | l1, [] -> l1 @@ accu 972 | h1::t1, h2::t2 -> 973 if cmp h1 h2 > 0 974 then rev_merge_rev t1 l2 (h1::accu) 975 else rev_merge_rev l1 t2 (h2::accu) 976 in 977 let rec sort n l = 978 match n, l with 979 | 2, x1 :: x2 :: _ -> 980 if cmp x1 x2 <= 0 then [x1; x2] else [x2; x1] 981 | 3, x1 :: x2 :: x3 :: _ -> 982 if cmp x1 x2 <= 0 then begin 983 if cmp x2 x3 <= 0 then [x1; x2; x3] 984 else if cmp x1 x3 <= 0 then [x1; x3; x2] 985 else [x3; x1; x2] 986 end else begin 987 if cmp x1 x3 <= 0 then [x2; x1; x3] 988 else if cmp x2 x3 <= 0 then [x2; x3; x1] 989 else [x3; x2; x1] 990 end 991 | n, l -> 992 let n1 = n asr 1 in 993 let n2 = n - n1 in 994 let l2 = chop n1 l in 995 let s1 = rev_sort n1 l in 996 let s2 = rev_sort n2 l2 in 997 rev_merge_rev s1 s2 [] 998 and rev_sort n l = 999 match n, l with 1000 | 2, x1 :: x2 :: _ -> 1001 if cmp x1 x2 > 0 then [x1; x2] else [x2; x1] 1002 | 3, x1 :: x2 :: x3 :: _ -> 1003 if cmp x1 x2 > 0 then begin 1004 if cmp x2 x3 > 0 then [x1; x2; x3] 1005 else if cmp x1 x3 > 0 then [x1; x3; x2] 1006 else [x3; x1; x2] 1007 end else begin 1008 if cmp x1 x3 > 0 then [x2; x1; x3] 1009 else if cmp x2 x3 > 0 then [x2; x3; x1] 1010 else [x3; x2; x1] 1011 end 1012 | n, l -> 1013 let n1 = n asr 1 in 1014 let n2 = n - n1 in 1015 let l2 = chop n1 l in 1016 let s1 = sort n1 l in 1017 let s2 = sort n2 l2 in 1018 rev_merge s1 s2 [] 1019 in 1020 let len = List.length l in 1021 if len < 2 then l else sort len l 1022;; 1023 1024(************************************************************************) 1025(* chop-free version of Pottier's code, binary version *) 1026 1027let rec merge cmp l1 l2 = 1028 match l1, l2 with 1029 | [], l2 -> l2 1030 | l1, [] -> l1 1031 | h1 :: t1, h2 :: t2 -> 1032 if cmp h1 h2 <= 0 1033 then h1 :: merge cmp t1 l2 1034 else h2 :: merge cmp l1 t2 1035;; 1036 1037let lmerge_5a cmp l = 1038 let rem = ref l in 1039 let rec sort_prefix n = 1040 if n <= 1 then begin 1041 match !rem with 1042 | [] -> [] 1043 | [x] as l -> rem := []; l 1044 | x::y::t -> rem := t; if cmp x y <= 0 then [x;y] else [y;x] 1045 end else if !rem = [] then [] 1046 else begin 1047 let l1 = sort_prefix (n-1) in 1048 let l2 = sort_prefix (n-1) in 1049 merge cmp l1 l2 1050 end 1051 in 1052 let len = ref (List.length l) in 1053 let i = ref 0 in 1054 while !len > 0 do incr i; len := !len lsr 1; done; 1055 sort_prefix !i 1056;; 1057 1058(************************************************************************) 1059(* chop-free version of Pottier's code, dichotomic version, 1060 ground cases 1 & 2 *) 1061 1062let rec merge cmp l1 l2 = 1063 match l1, l2 with 1064 | [], l2 -> l2 1065 | l1, [] -> l1 1066 | h1 :: t1, h2 :: t2 -> 1067 if cmp h1 h2 <= 0 1068 then h1 :: merge cmp t1 l2 1069 else h2 :: merge cmp l1 t2 1070;; 1071 1072let lmerge_5b cmp l = 1073 let rem = ref l in 1074 let rec sort_prefix n = 1075 match n, !rem with 1076 | 1, x::t -> rem := t; [x] 1077 | 2, x::y::t -> rem := t; if cmp x y <= 0 then [x;y] else [y;x] 1078 | n, _ -> 1079 let n1 = n/2 in 1080 let n2 = n - n1 in 1081 let l1 = sort_prefix n1 in 1082 let l2 = sort_prefix n2 in 1083 merge cmp l1 l2 1084 in 1085 let len = List.length l in 1086 if len <= 1 then l else sort_prefix len 1087;; 1088 1089(************************************************************************) 1090(* chop-free version of Pottier's code, dichotomic version, 1091 ground cases 2 & 3 *) 1092 1093let rec merge cmp l1 l2 = 1094 match l1, l2 with 1095 | [], l2 -> l2 1096 | l1, [] -> l1 1097 | h1 :: t1, h2 :: t2 -> 1098 if cmp h1 h2 <= 0 1099 then h1 :: merge cmp t1 l2 1100 else h2 :: merge cmp l1 t2 1101;; 1102 1103let lmerge_5c cmp l = 1104 let rem = ref l in 1105 let rec sort_prefix n = 1106 match n, !rem with 1107 | 2, x::y::t -> rem := t; if cmp x y <= 0 then [x;y] else [y;x] 1108 | 3, x::y::z::t -> 1109 rem := t; 1110 if cmp x y <= 0 then 1111 if cmp y z <= 0 then [x; y; z] 1112 else if cmp x z <= 0 then [x; z; y] 1113 else [z; x; y] 1114 else 1115 if cmp x z <= 0 then [y; x; z] 1116 else if cmp y z <= 0 then [y; z; x] 1117 else [z; y; x] 1118 | n, _ -> 1119 let n1 = n/2 in 1120 let n2 = n - n1 in 1121 let l1 = sort_prefix n1 in 1122 let l2 = sort_prefix n2 in 1123 merge cmp l1 l2 1124 in 1125 let len = List.length l in 1126 if len <= 1 then l else sort_prefix len 1127;; 1128 1129(************************************************************************) 1130(* chop-free, ref-free version of Pottier's code, dichotomic version, 1131 ground cases 2 & 3, modified merge *) 1132 1133let lmerge_5d cmp l = 1134 let rec merge1 h1 t1 l2 = 1135 match l2 with 1136 | [] -> h1::t1 1137 | h2 :: t2 -> 1138 if cmp h1 h2 <= 0 1139 then h1 :: merge2 t1 h2 t2 1140 else h2 :: merge1 h1 t1 t2 1141 and merge2 l1 h2 t2 = 1142 match l1 with 1143 | [] -> h2::t2 1144 | h1 :: t1 -> 1145 if cmp h1 h2 <= 0 1146 then h1 :: merge2 t1 h2 t2 1147 else h2 :: merge1 h1 t1 t2 1148 in 1149 let rec sort_prefix n l = 1150 match n, l with 1151 | 2, x::y::t -> ((if cmp x y <= 0 then [x;y] else [y;x]), t) 1152 | 3, x::y::z::t -> 1153 ((if cmp x y <= 0 then 1154 if cmp y z <= 0 then [x; y; z] 1155 else if cmp x z <= 0 then [x; z; y] 1156 else [z; x; y] 1157 else 1158 if cmp x z <= 0 then [y; x; z] 1159 else if cmp y z <= 0 then [y; z; x] 1160 else [z; y; x]), 1161 t) 1162 | n, _ -> 1163 let n1 = n/2 in 1164 let n2 = n - n1 in 1165 let (l1, rest1) = sort_prefix n1 l in 1166 match sort_prefix n2 rest1 with 1167 | (h2::t2, rest2) -> ((merge2 l1 h2 t2), rest2) 1168 | _ -> assert false 1169 in 1170 let len = List.length l in 1171 if len <= 1 then l else fst (sort_prefix len l) 1172;; 1173 1174(************************************************************************) 1175(* merge sort on arrays, merge with tail-rec function *) 1176 1177let amerge_1a cmp a = 1178 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1179 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1180 let rec loop i1 s1 i2 s2 d = 1181 if cmp s1 s2 <= 0 then begin 1182 dst.(d) <- s1; 1183 let i1 = i1 + 1 in 1184 if i1 < src1r then 1185 loop i1 a.(i1) i2 s2 (d + 1) 1186 else 1187 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1188 end else begin 1189 dst.(d) <- s2; 1190 let i2 = i2 + 1 in 1191 if i2 < src2r then 1192 loop i1 s1 i2 src2.(i2) (d + 1) 1193 else 1194 Array.blit a i1 dst (d + 1) (src1r - i1) 1195 end 1196 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1197 in 1198 let rec sortto srcofs dst dstofs len = 1199 assert (len > 0); 1200 if len = 1 then dst.(dstofs) <- a.(srcofs) 1201 else begin 1202 let l1 = len / 2 in 1203 let l2 = len - l1 in 1204 sortto (srcofs + l1) dst (dstofs + l1) l2; 1205 sortto srcofs a (srcofs + l2) l1; 1206 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1207 end; 1208 in 1209 let l = Array.length a in 1210 if l <= 1 then () 1211 else begin 1212 let l1 = l / 2 in 1213 let l2 = l - l1 in 1214 let t = Array.make l2 a.(0) in 1215 sortto l1 t 0 l2; 1216 sortto 0 a l2 l1; 1217 merge l2 l1 t 0 l2 a 0; 1218 end; 1219;; 1220 1221let amerge_1b cmp a = 1222 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1223 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1224 let rec loop i1 s1 i2 s2 d = 1225 if cmp s1 s2 <= 0 then begin 1226 dst.(d) <- s1; 1227 let i1 = i1 + 1 in 1228 if i1 < src1r then 1229 loop i1 a.(i1) i2 s2 (d + 1) 1230 else 1231 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1232 end else begin 1233 dst.(d) <- s2; 1234 let i2 = i2 + 1 in 1235 if i2 < src2r then 1236 loop i1 s1 i2 src2.(i2) (d + 1) 1237 else 1238 Array.blit a i1 dst (d + 1) (src1r - i1) 1239 end 1240 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1241 in 1242 let rec sortto srcofs dst dstofs len = 1243 assert (len > 0); 1244 if len = 1 then dst.(dstofs) <- a.(srcofs) 1245 else if len = 2 then begin 1246 if cmp a.(srcofs) a.(srcofs+1) <= 0 then begin 1247 dst.(dstofs) <- a.(srcofs); 1248 dst.(dstofs+1) <- a.(srcofs+1); 1249 end else begin 1250 dst.(dstofs) <- a.(srcofs+1); 1251 dst.(dstofs+1) <- a.(srcofs); 1252 end; 1253 end else begin 1254 let l1 = len / 2 in 1255 let l2 = len - l1 in 1256 sortto (srcofs + l1) dst (dstofs + l1) l2; 1257 sortto srcofs a (srcofs + l2) l1; 1258 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1259 end; 1260 in 1261 let l = Array.length a in 1262 if l <= 1 then () 1263 else if l = 2 then begin 1264 if cmp a.(0) a.(1) > 0 then begin 1265 let e = a.(0) in 1266 a.(0) <- a.(1); 1267 a.(1) <- e; 1268 end; 1269 end else begin 1270 let l1 = l / 2 in 1271 let l2 = l - l1 in 1272 let t = Array.make l2 a.(0) in 1273 sortto l1 t 0 l2; 1274 sortto 0 a l2 l1; 1275 merge l2 l1 t 0 l2 a 0; 1276 end; 1277;; 1278 1279let cutoff = 3;; 1280let amerge_1c cmp a = 1281 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1282 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1283 let rec loop i1 s1 i2 s2 d = 1284 if cmp s1 s2 <= 0 then begin 1285 dst.(d) <- s1; 1286 let i1 = i1 + 1 in 1287 if i1 < src1r then 1288 loop i1 a.(i1) i2 s2 (d + 1) 1289 else 1290 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1291 end else begin 1292 dst.(d) <- s2; 1293 let i2 = i2 + 1 in 1294 if i2 < src2r then 1295 loop i1 s1 i2 src2.(i2) (d + 1) 1296 else 1297 Array.blit a i1 dst (d + 1) (src1r - i1) 1298 end 1299 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1300 in 1301 let isortto srcofs dst dstofs len = 1302 for i = 0 to len - 1 do 1303 let e = a.(srcofs + i) in 1304 let j = ref (dstofs + i - 1) in 1305 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1306 dst.(!j + 1) <- dst.(!j); 1307 decr j; 1308 done; 1309 dst.(!j + 1) <- e; 1310 done; 1311 in 1312 let rec sortto srcofs dst dstofs len = 1313 if len <= cutoff then isortto srcofs dst dstofs len else begin 1314 let l1 = len / 2 in 1315 let l2 = len - l1 in 1316 sortto (srcofs + l1) dst (dstofs + l1) l2; 1317 sortto srcofs a (srcofs + l2) l1; 1318 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1319 end; 1320 in 1321 let l = Array.length a in 1322 if l <= cutoff then isortto 0 a 0 l else begin 1323 let l1 = l / 2 in 1324 let l2 = l - l1 in 1325 let t = Array.make l2 a.(0) in 1326 sortto l1 t 0 l2; 1327 sortto 0 a l2 l1; 1328 merge l2 l1 t 0 l2 a 0; 1329 end; 1330;; 1331 1332let cutoff = 4;; 1333let amerge_1d cmp a = 1334 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1335 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1336 let rec loop i1 s1 i2 s2 d = 1337 if cmp s1 s2 <= 0 then begin 1338 dst.(d) <- s1; 1339 let i1 = i1 + 1 in 1340 if i1 < src1r then 1341 loop i1 a.(i1) i2 s2 (d + 1) 1342 else 1343 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1344 end else begin 1345 dst.(d) <- s2; 1346 let i2 = i2 + 1 in 1347 if i2 < src2r then 1348 loop i1 s1 i2 src2.(i2) (d + 1) 1349 else 1350 Array.blit a i1 dst (d + 1) (src1r - i1) 1351 end 1352 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1353 in 1354 let isortto srcofs dst dstofs len = 1355 for i = 0 to len - 1 do 1356 let e = a.(srcofs + i) in 1357 let j = ref (dstofs + i - 1) in 1358 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1359 dst.(!j + 1) <- dst.(!j); 1360 decr j; 1361 done; 1362 dst.(!j + 1) <- e; 1363 done; 1364 in 1365 let rec sortto srcofs dst dstofs len = 1366 if len <= cutoff then isortto srcofs dst dstofs len else begin 1367 let l1 = len / 2 in 1368 let l2 = len - l1 in 1369 sortto (srcofs + l1) dst (dstofs + l1) l2; 1370 sortto srcofs a (srcofs + l2) l1; 1371 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1372 end; 1373 in 1374 let l = Array.length a in 1375 if l <= cutoff then isortto 0 a 0 l else begin 1376 let l1 = l / 2 in 1377 let l2 = l - l1 in 1378 let t = Array.make l2 a.(0) in 1379 sortto l1 t 0 l2; 1380 sortto 0 a l2 l1; 1381 merge l2 l1 t 0 l2 a 0; 1382 end; 1383;; 1384 1385let cutoff = 5;; 1386let amerge_1e cmp a = 1387 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1388 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1389 let rec loop i1 s1 i2 s2 d = 1390 if cmp s1 s2 <= 0 then begin 1391 dst.(d) <- s1; 1392 let i1 = i1 + 1 in 1393 if i1 < src1r then 1394 loop i1 a.(i1) i2 s2 (d + 1) 1395 else 1396 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1397 end else begin 1398 dst.(d) <- s2; 1399 let i2 = i2 + 1 in 1400 if i2 < src2r then 1401 loop i1 s1 i2 src2.(i2) (d + 1) 1402 else 1403 Array.blit a i1 dst (d + 1) (src1r - i1) 1404 end 1405 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1406 in 1407 let isortto srcofs dst dstofs len = 1408 for i = 0 to len - 1 do 1409 let e = a.(srcofs + i) in 1410 let j = ref (dstofs + i - 1) in 1411 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1412 dst.(!j + 1) <- dst.(!j); 1413 decr j; 1414 done; 1415 dst.(!j + 1) <- e; 1416 done; 1417 in 1418 let rec sortto srcofs dst dstofs len = 1419 if len <= cutoff then isortto srcofs dst dstofs len else begin 1420 let l1 = len / 2 in 1421 let l2 = len - l1 in 1422 sortto (srcofs + l1) dst (dstofs + l1) l2; 1423 sortto srcofs a (srcofs + l2) l1; 1424 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1425 end; 1426 in 1427 let l = Array.length a in 1428 if l <= cutoff then isortto 0 a 0 l else begin 1429 let l1 = l / 2 in 1430 let l2 = l - l1 in 1431 let t = Array.make l2 a.(0) in 1432 sortto l1 t 0 l2; 1433 sortto 0 a l2 l1; 1434 merge l2 l1 t 0 l2 a 0; 1435 end; 1436;; 1437 1438let cutoff = 6;; 1439let amerge_1f cmp a = 1440 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1441 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1442 let rec loop i1 s1 i2 s2 d = 1443 if cmp s1 s2 <= 0 then begin 1444 dst.(d) <- s1; 1445 let i1 = i1 + 1 in 1446 if i1 < src1r then 1447 loop i1 a.(i1) i2 s2 (d + 1) 1448 else 1449 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1450 end else begin 1451 dst.(d) <- s2; 1452 let i2 = i2 + 1 in 1453 if i2 < src2r then 1454 loop i1 s1 i2 src2.(i2) (d + 1) 1455 else 1456 Array.blit a i1 dst (d + 1) (src1r - i1) 1457 end 1458 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1459 in 1460 let isortto srcofs dst dstofs len = 1461 for i = 0 to len - 1 do 1462 let e = a.(srcofs + i) in 1463 let j = ref (dstofs + i - 1) in 1464 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1465 dst.(!j + 1) <- dst.(!j); 1466 decr j; 1467 done; 1468 dst.(!j + 1) <- e; 1469 done; 1470 in 1471 let rec sortto srcofs dst dstofs len = 1472 if len <= cutoff then isortto srcofs dst dstofs len else begin 1473 let l1 = len / 2 in 1474 let l2 = len - l1 in 1475 sortto (srcofs + l1) dst (dstofs + l1) l2; 1476 sortto srcofs a (srcofs + l2) l1; 1477 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1478 end; 1479 in 1480 let l = Array.length a in 1481 if l <= cutoff then isortto 0 a 0 l else begin 1482 let l1 = l / 2 in 1483 let l2 = l - l1 in 1484 let t = Array.make l2 a.(0) in 1485 sortto l1 t 0 l2; 1486 sortto 0 a l2 l1; 1487 merge l2 l1 t 0 l2 a 0; 1488 end; 1489;; 1490 1491let cutoff = 7;; 1492let amerge_1g cmp a = 1493 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1494 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1495 let rec loop i1 s1 i2 s2 d = 1496 if cmp s1 s2 <= 0 then begin 1497 dst.(d) <- s1; 1498 let i1 = i1 + 1 in 1499 if i1 < src1r then 1500 loop i1 a.(i1) i2 s2 (d + 1) 1501 else 1502 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1503 end else begin 1504 dst.(d) <- s2; 1505 let i2 = i2 + 1 in 1506 if i2 < src2r then 1507 loop i1 s1 i2 src2.(i2) (d + 1) 1508 else 1509 Array.blit a i1 dst (d + 1) (src1r - i1) 1510 end 1511 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1512 in 1513 let isortto srcofs dst dstofs len = 1514 for i = 0 to len - 1 do 1515 let e = a.(srcofs + i) in 1516 let j = ref (dstofs + i - 1) in 1517 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1518 dst.(!j + 1) <- dst.(!j); 1519 decr j; 1520 done; 1521 dst.(!j + 1) <- e; 1522 done; 1523 in 1524 let rec sortto srcofs dst dstofs len = 1525 if len <= cutoff then isortto srcofs dst dstofs len else begin 1526 let l1 = len / 2 in 1527 let l2 = len - l1 in 1528 sortto (srcofs + l1) dst (dstofs + l1) l2; 1529 sortto srcofs a (srcofs + l2) l1; 1530 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1531 end; 1532 in 1533 let l = Array.length a in 1534 if l <= cutoff then isortto 0 a 0 l else begin 1535 let l1 = l / 2 in 1536 let l2 = l - l1 in 1537 let t = Array.make l2 a.(0) in 1538 sortto l1 t 0 l2; 1539 sortto 0 a l2 l1; 1540 merge l2 l1 t 0 l2 a 0; 1541 end; 1542;; 1543 1544let cutoff = 8;; 1545let amerge_1h cmp a = 1546 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1547 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1548 let rec loop i1 s1 i2 s2 d = 1549 if cmp s1 s2 <= 0 then begin 1550 dst.(d) <- s1; 1551 let i1 = i1 + 1 in 1552 if i1 < src1r then 1553 loop i1 a.(i1) i2 s2 (d + 1) 1554 else 1555 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1556 end else begin 1557 dst.(d) <- s2; 1558 let i2 = i2 + 1 in 1559 if i2 < src2r then 1560 loop i1 s1 i2 src2.(i2) (d + 1) 1561 else 1562 Array.blit a i1 dst (d + 1) (src1r - i1) 1563 end 1564 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1565 in 1566 let isortto srcofs dst dstofs len = 1567 for i = 0 to len - 1 do 1568 let e = a.(srcofs + i) in 1569 let j = ref (dstofs + i - 1) in 1570 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1571 dst.(!j + 1) <- dst.(!j); 1572 decr j; 1573 done; 1574 dst.(!j + 1) <- e; 1575 done; 1576 in 1577 let rec sortto srcofs dst dstofs len = 1578 if len <= cutoff then isortto srcofs dst dstofs len else begin 1579 let l1 = len / 2 in 1580 let l2 = len - l1 in 1581 sortto (srcofs + l1) dst (dstofs + l1) l2; 1582 sortto srcofs a (srcofs + l2) l1; 1583 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1584 end; 1585 in 1586 let l = Array.length a in 1587 if l <= cutoff then isortto 0 a 0 l else begin 1588 let l1 = l / 2 in 1589 let l2 = l - l1 in 1590 let t = Array.make l2 a.(0) in 1591 sortto l1 t 0 l2; 1592 sortto 0 a l2 l1; 1593 merge l2 l1 t 0 l2 a 0; 1594 end; 1595;; 1596 1597let cutoff = 9;; 1598let amerge_1i cmp a = 1599 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1600 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1601 let rec loop i1 s1 i2 s2 d = 1602 if cmp s1 s2 <= 0 then begin 1603 dst.(d) <- s1; 1604 let i1 = i1 + 1 in 1605 if i1 < src1r then 1606 loop i1 a.(i1) i2 s2 (d + 1) 1607 else 1608 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1609 end else begin 1610 dst.(d) <- s2; 1611 let i2 = i2 + 1 in 1612 if i2 < src2r then 1613 loop i1 s1 i2 src2.(i2) (d + 1) 1614 else 1615 Array.blit a i1 dst (d + 1) (src1r - i1) 1616 end 1617 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1618 in 1619 let isortto srcofs dst dstofs len = 1620 for i = 0 to len - 1 do 1621 let e = a.(srcofs + i) in 1622 let j = ref (dstofs + i - 1) in 1623 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1624 dst.(!j + 1) <- dst.(!j); 1625 decr j; 1626 done; 1627 dst.(!j + 1) <- e; 1628 done; 1629 in 1630 let rec sortto srcofs dst dstofs len = 1631 if len <= cutoff then isortto srcofs dst dstofs len else begin 1632 let l1 = len / 2 in 1633 let l2 = len - l1 in 1634 sortto (srcofs + l1) dst (dstofs + l1) l2; 1635 sortto srcofs a (srcofs + l2) l1; 1636 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1637 end; 1638 in 1639 let l = Array.length a in 1640 if l <= cutoff then isortto 0 a 0 l else begin 1641 let l1 = l / 2 in 1642 let l2 = l - l1 in 1643 let t = Array.make l2 a.(0) in 1644 sortto l1 t 0 l2; 1645 sortto 0 a l2 l1; 1646 merge l2 l1 t 0 l2 a 0; 1647 end; 1648;; 1649 1650let cutoff = 10;; 1651let amerge_1j cmp a = 1652 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1653 let src1r = src1ofs + src1len and src2r = src2ofs + src2len in 1654 let rec loop i1 s1 i2 s2 d = 1655 if cmp s1 s2 <= 0 then begin 1656 dst.(d) <- s1; 1657 let i1 = i1 + 1 in 1658 if i1 < src1r then 1659 loop i1 a.(i1) i2 s2 (d + 1) 1660 else 1661 Array.blit src2 i2 dst (d + 1) (src2r - i2) 1662 end else begin 1663 dst.(d) <- s2; 1664 let i2 = i2 + 1 in 1665 if i2 < src2r then 1666 loop i1 s1 i2 src2.(i2) (d + 1) 1667 else 1668 Array.blit a i1 dst (d + 1) (src1r - i1) 1669 end 1670 in loop src1ofs a.(src1ofs) src2ofs src2.(src2ofs) dstofs; 1671 in 1672 let isortto srcofs dst dstofs len = 1673 for i = 0 to len - 1 do 1674 let e = a.(srcofs + i) in 1675 let j = ref (dstofs + i - 1) in 1676 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1677 dst.(!j + 1) <- dst.(!j); 1678 decr j; 1679 done; 1680 dst.(!j + 1) <- e; 1681 done; 1682 in 1683 let rec sortto srcofs dst dstofs len = 1684 if len <= cutoff then isortto srcofs dst dstofs len else begin 1685 let l1 = len / 2 in 1686 let l2 = len - l1 in 1687 sortto (srcofs + l1) dst (dstofs + l1) l2; 1688 sortto srcofs a (srcofs + l2) l1; 1689 merge (srcofs + l2) l1 dst (dstofs + l1) l2 dst dstofs; 1690 end; 1691 in 1692 let l = Array.length a in 1693 if l <= cutoff then isortto 0 a 0 l else begin 1694 let l1 = l / 2 in 1695 let l2 = l - l1 in 1696 let t = Array.make l2 a.(0) in 1697 sortto l1 t 0 l2; 1698 sortto 0 a l2 l1; 1699 merge l2 l1 t 0 l2 a 0; 1700 end; 1701;; 1702 1703(* FIXME try: *) 1704(* list->array->list direct and array->list->array direct *) 1705(* overhead = 1/3, 1/4, etc. *) 1706(* overhead = sqrt (n) *) 1707(* overhead = n/3 up to 30k, 30k up to 900M, sqrt (n) beyond *) 1708 1709(************************************************************************) 1710(* merge sort on arrays, merge with loop *) 1711 1712(* cutoff = 1 *) 1713let amerge_3a cmp a = 1714 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1715 let i1 = ref src1ofs 1716 and i2 = ref src2ofs 1717 and d = ref dstofs 1718 and src1r = src1ofs + src1len 1719 and src2r = src2ofs + src2len 1720 in 1721 while !i1 < src1r && !i2 < src2r do 1722 let s1 = a.(!i1) and s2 = src2.(!i2) in 1723 if cmp s1 s2 <= 0 then begin 1724 dst.(!d) <- s1; 1725 incr i1; 1726 end else begin 1727 dst.(!d) <- s2; 1728 incr i2; 1729 end; 1730 incr d; 1731 done; 1732 if !i1 < src1r then 1733 Array.blit a !i1 dst !d (src1r - !i1) 1734 else 1735 Array.blit src2 !i2 dst !d (src2r - !i2) 1736 in 1737 let rec sortto srcofs dst dstofs len = 1738 assert (len > 0); 1739 if len = 1 then dst.(dstofs) <- a.(srcofs) else 1740 let l1 = len / 2 in 1741 let l2 = len - l1 in 1742 sortto (srcofs+l1) dst (dstofs+l1) l2; 1743 sortto srcofs a (srcofs+l2) l1; 1744 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 1745 in 1746 let l = Array.length a in 1747 if l <= 1 then () else begin 1748 let l1 = l / 2 in 1749 let l2 = l - l1 in 1750 let t = Array.make l2 a.(0) in 1751 sortto l1 t 0 l2; 1752 sortto 0 a l2 l1; 1753 merge l2 l1 t 0 l2 a 0; 1754 end; 1755;; 1756 1757let amerge_3b cmp a = 1758 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1759 let i1 = ref src1ofs 1760 and i2 = ref src2ofs 1761 and d = ref dstofs 1762 and src1r = src1ofs + src1len 1763 and src2r = src2ofs + src2len 1764 in 1765 while !i1 < src1r && !i2 < src2r do 1766 let s1 = a.(!i1) and s2 = src2.(!i2) in 1767 if cmp s1 s2 <= 0 then begin 1768 dst.(!d) <- s1; 1769 incr i1; 1770 end else begin 1771 dst.(!d) <- s2; 1772 incr i2; 1773 end; 1774 incr d; 1775 done; 1776 if !i1 < src1r then 1777 Array.blit a !i1 dst !d (src1r - !i1) 1778 else 1779 Array.blit src2 !i2 dst !d (src2r - !i2) 1780 in 1781 let rec sortto srcofs dst dstofs len = 1782 assert (len > 0); 1783 if len = 1 then dst.(dstofs) <- a.(srcofs) 1784 else if len = 2 then begin 1785 if cmp a.(srcofs) a.(srcofs+1) <= 0 then begin 1786 dst.(dstofs) <- a.(srcofs); 1787 dst.(dstofs+1) <- a.(srcofs+1); 1788 end else begin 1789 dst.(dstofs) <- a.(srcofs+1); 1790 dst.(dstofs+1) <- a.(srcofs); 1791 end 1792 end else begin 1793 let l1 = len / 2 in 1794 let l2 = len - l1 in 1795 sortto (srcofs+l1) dst (dstofs+l1) l2; 1796 sortto srcofs a (srcofs+l2) l1; 1797 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 1798 end 1799 in 1800 let l = Array.length a in 1801 if l <= 1 then () 1802 else if l = 2 then begin 1803 if cmp a.(0) a.(1) > 0 then begin 1804 let e = a.(0) in 1805 a.(0) <- a.(1); 1806 a.(1) <- e; 1807 end; 1808 end else begin 1809 let l1 = l / 2 in 1810 let l2 = l - l1 in 1811 let t = Array.make l2 a.(0) in 1812 sortto l1 t 0 l2; 1813 sortto 0 a l2 l1; 1814 merge l2 l1 t 0 l2 a 0; 1815 end; 1816;; 1817 1818let cutoff = 3;; 1819let amerge_3c cmp a = 1820 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1821 let i1 = ref src1ofs 1822 and i2 = ref src2ofs 1823 and d = ref dstofs 1824 and src1r = src1ofs + src1len 1825 and src2r = src2ofs + src2len 1826 in 1827 while !i1 < src1r && !i2 < src2r do 1828 let s1 = a.(!i1) and s2 = src2.(!i2) in 1829 if cmp s1 s2 <= 0 then begin 1830 dst.(!d) <- s1; 1831 incr i1; 1832 end else begin 1833 dst.(!d) <- s2; 1834 incr i2; 1835 end; 1836 incr d; 1837 done; 1838 if !i1 < src1r then 1839 Array.blit a !i1 dst !d (src1r - !i1) 1840 else 1841 Array.blit src2 !i2 dst !d (src2r - !i2) 1842 in 1843 let isortto srcofs dst dstofs len = 1844 for i = 0 to len-1 do 1845 let e = a.(srcofs+i) in 1846 let j = ref (dstofs+i-1) in 1847 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1848 dst.(!j + 1) <- dst.(!j); 1849 decr j; 1850 done; 1851 dst.(!j + 1) <- e; 1852 done; 1853 in 1854 let rec sortto srcofs dst dstofs len = 1855 if len <= cutoff then isortto srcofs dst dstofs len else 1856 let l1 = len / 2 in 1857 let l2 = len - l1 in 1858 sortto (srcofs+l1) dst (dstofs+l1) l2; 1859 sortto srcofs a (srcofs+l2) l1; 1860 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 1861 in 1862 let l = Array.length a in 1863 if l <= cutoff then isortto 0 a 0 l else begin 1864 let l1 = l / 2 in 1865 let l2 = l - l1 in 1866 let t = Array.make l2 a.(0) in 1867 sortto l1 t 0 l2; 1868 sortto 0 a l2 l1; 1869 merge l2 l1 t 0 l2 a 0; 1870 end; 1871;; 1872 1873let cutoff = 4;; 1874let amerge_3d cmp a = 1875 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1876 let i1 = ref src1ofs 1877 and i2 = ref src2ofs 1878 and d = ref dstofs 1879 and src1r = src1ofs + src1len 1880 and src2r = src2ofs + src2len 1881 in 1882 while !i1 < src1r && !i2 < src2r do 1883 let s1 = a.(!i1) and s2 = src2.(!i2) in 1884 if cmp s1 s2 <= 0 then begin 1885 dst.(!d) <- s1; 1886 incr i1; 1887 end else begin 1888 dst.(!d) <- s2; 1889 incr i2; 1890 end; 1891 incr d; 1892 done; 1893 if !i1 < src1r then 1894 Array.blit a !i1 dst !d (src1r - !i1) 1895 else 1896 Array.blit src2 !i2 dst !d (src2r - !i2) 1897 in 1898 let isortto srcofs dst dstofs len = 1899 for i = 0 to len-1 do 1900 let e = a.(srcofs+i) in 1901 let j = ref (dstofs+i-1) in 1902 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1903 dst.(!j + 1) <- dst.(!j); 1904 decr j; 1905 done; 1906 dst.(!j + 1) <- e; 1907 done; 1908 in 1909 let rec sortto srcofs dst dstofs len = 1910 if len <= cutoff then isortto srcofs dst dstofs len else 1911 let l1 = len / 2 in 1912 let l2 = len - l1 in 1913 sortto (srcofs+l1) dst (dstofs+l1) l2; 1914 sortto srcofs a (srcofs+l2) l1; 1915 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 1916 in 1917 let l = Array.length a in 1918 if l <= cutoff then isortto 0 a 0 l else begin 1919 let l1 = l / 2 in 1920 let l2 = l - l1 in 1921 let t = Array.make l2 a.(0) in 1922 sortto l1 t 0 l2; 1923 sortto 0 a l2 l1; 1924 merge l2 l1 t 0 l2 a 0; 1925 end; 1926;; 1927 1928let cutoff = 5;; 1929let amerge_3e cmp a = 1930 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1931 let i1 = ref src1ofs 1932 and i2 = ref src2ofs 1933 and d = ref dstofs 1934 and src1r = src1ofs + src1len 1935 and src2r = src2ofs + src2len 1936 in 1937 while !i1 < src1r && !i2 < src2r do 1938 let s1 = a.(!i1) and s2 = src2.(!i2) in 1939 if cmp s1 s2 <= 0 then begin 1940 dst.(!d) <- s1; 1941 incr i1; 1942 end else begin 1943 dst.(!d) <- s2; 1944 incr i2; 1945 end; 1946 incr d; 1947 done; 1948 if !i1 < src1r then 1949 Array.blit a !i1 dst !d (src1r - !i1) 1950 else 1951 Array.blit src2 !i2 dst !d (src2r - !i2) 1952 in 1953 let isortto srcofs dst dstofs len = 1954 for i = 0 to len-1 do 1955 let e = a.(srcofs+i) in 1956 let j = ref (dstofs+i-1) in 1957 while (!j >= dstofs && cmp dst.(!j) e > 0) do 1958 dst.(!j + 1) <- dst.(!j); 1959 decr j; 1960 done; 1961 dst.(!j + 1) <- e; 1962 done; 1963 in 1964 let rec sortto srcofs dst dstofs len = 1965 if len <= cutoff then isortto srcofs dst dstofs len else 1966 let l1 = len / 2 in 1967 let l2 = len - l1 in 1968 sortto (srcofs+l1) dst (dstofs+l1) l2; 1969 sortto srcofs a (srcofs+l2) l1; 1970 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 1971 in 1972 let l = Array.length a in 1973 if l <= cutoff then isortto 0 a 0 l else begin 1974 let l1 = l / 2 in 1975 let l2 = l - l1 in 1976 let t = Array.make l2 a.(0) in 1977 sortto l1 t 0 l2; 1978 sortto 0 a l2 l1; 1979 merge l2 l1 t 0 l2 a 0; 1980 end; 1981;; 1982 1983let cutoff = 6;; 1984let amerge_3f cmp a = 1985 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 1986 let i1 = ref src1ofs 1987 and i2 = ref src2ofs 1988 and d = ref dstofs 1989 and src1r = src1ofs + src1len 1990 and src2r = src2ofs + src2len 1991 in 1992 while !i1 < src1r && !i2 < src2r do 1993 let s1 = a.(!i1) and s2 = src2.(!i2) in 1994 if cmp s1 s2 <= 0 then begin 1995 dst.(!d) <- s1; 1996 incr i1; 1997 end else begin 1998 dst.(!d) <- s2; 1999 incr i2; 2000 end; 2001 incr d; 2002 done; 2003 if !i1 < src1r then 2004 Array.blit a !i1 dst !d (src1r - !i1) 2005 else 2006 Array.blit src2 !i2 dst !d (src2r - !i2) 2007 in 2008 let isortto srcofs dst dstofs len = 2009 for i = 0 to len-1 do 2010 let e = a.(srcofs+i) in 2011 let j = ref (dstofs+i-1) in 2012 while (!j >= dstofs && cmp dst.(!j) e > 0) do 2013 dst.(!j + 1) <- dst.(!j); 2014 decr j; 2015 done; 2016 dst.(!j + 1) <- e; 2017 done; 2018 in 2019 let rec sortto srcofs dst dstofs len = 2020 if len <= cutoff then isortto srcofs dst dstofs len else 2021 let l1 = len / 2 in 2022 let l2 = len - l1 in 2023 sortto (srcofs+l1) dst (dstofs+l1) l2; 2024 sortto srcofs a (srcofs+l2) l1; 2025 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 2026 in 2027 let l = Array.length a in 2028 if l <= cutoff then isortto 0 a 0 l else begin 2029 let l1 = l / 2 in 2030 let l2 = l - l1 in 2031 let t = Array.make l2 a.(0) in 2032 sortto l1 t 0 l2; 2033 sortto 0 a l2 l1; 2034 merge l2 l1 t 0 l2 a 0; 2035 end; 2036;; 2037 2038let cutoff = 7;; 2039let amerge_3g cmp a = 2040 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 2041 let i1 = ref src1ofs 2042 and i2 = ref src2ofs 2043 and d = ref dstofs 2044 and src1r = src1ofs + src1len 2045 and src2r = src2ofs + src2len 2046 in 2047 while !i1 < src1r && !i2 < src2r do 2048 let s1 = a.(!i1) and s2 = src2.(!i2) in 2049 if cmp s1 s2 <= 0 then begin 2050 dst.(!d) <- s1; 2051 incr i1; 2052 end else begin 2053 dst.(!d) <- s2; 2054 incr i2; 2055 end; 2056 incr d; 2057 done; 2058 if !i1 < src1r then 2059 Array.blit a !i1 dst !d (src1r - !i1) 2060 else 2061 Array.blit src2 !i2 dst !d (src2r - !i2) 2062 in 2063 let isortto srcofs dst dstofs len = 2064 for i = 0 to len-1 do 2065 let e = a.(srcofs+i) in 2066 let j = ref (dstofs+i-1) in 2067 while (!j >= dstofs && cmp dst.(!j) e > 0) do 2068 dst.(!j + 1) <- dst.(!j); 2069 decr j; 2070 done; 2071 dst.(!j + 1) <- e; 2072 done; 2073 in 2074 let rec sortto srcofs dst dstofs len = 2075 if len <= cutoff then isortto srcofs dst dstofs len else 2076 let l1 = len / 2 in 2077 let l2 = len - l1 in 2078 sortto (srcofs+l1) dst (dstofs+l1) l2; 2079 sortto srcofs a (srcofs+l2) l1; 2080 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 2081 in 2082 let l = Array.length a in 2083 if l <= cutoff then isortto 0 a 0 l else begin 2084 let l1 = l / 2 in 2085 let l2 = l - l1 in 2086 let t = Array.make l2 a.(0) in 2087 sortto l1 t 0 l2; 2088 sortto 0 a l2 l1; 2089 merge l2 l1 t 0 l2 a 0; 2090 end; 2091;; 2092 2093let cutoff = 8;; 2094let amerge_3h cmp a = 2095 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 2096 let i1 = ref src1ofs 2097 and i2 = ref src2ofs 2098 and d = ref dstofs 2099 and src1r = src1ofs + src1len 2100 and src2r = src2ofs + src2len 2101 in 2102 while !i1 < src1r && !i2 < src2r do 2103 let s1 = a.(!i1) and s2 = src2.(!i2) in 2104 if cmp s1 s2 <= 0 then begin 2105 dst.(!d) <- s1; 2106 incr i1; 2107 end else begin 2108 dst.(!d) <- s2; 2109 incr i2; 2110 end; 2111 incr d; 2112 done; 2113 if !i1 < src1r then 2114 Array.blit a !i1 dst !d (src1r - !i1) 2115 else 2116 Array.blit src2 !i2 dst !d (src2r - !i2) 2117 in 2118 let isortto srcofs dst dstofs len = 2119 for i = 0 to len-1 do 2120 let e = a.(srcofs+i) in 2121 let j = ref (dstofs+i-1) in 2122 while (!j >= dstofs && cmp dst.(!j) e > 0) do 2123 dst.(!j + 1) <- dst.(!j); 2124 decr j; 2125 done; 2126 dst.(!j + 1) <- e; 2127 done; 2128 in 2129 let rec sortto srcofs dst dstofs len = 2130 if len <= cutoff then isortto srcofs dst dstofs len else 2131 let l1 = len / 2 in 2132 let l2 = len - l1 in 2133 sortto (srcofs+l1) dst (dstofs+l1) l2; 2134 sortto srcofs a (srcofs+l2) l1; 2135 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 2136 in 2137 let l = Array.length a in 2138 if l <= cutoff then isortto 0 a 0 l else begin 2139 let l1 = l / 2 in 2140 let l2 = l - l1 in 2141 let t = Array.make l2 a.(0) in 2142 sortto l1 t 0 l2; 2143 sortto 0 a l2 l1; 2144 merge l2 l1 t 0 l2 a 0; 2145 end; 2146;; 2147 2148let cutoff = 9;; 2149let amerge_3i cmp a = 2150 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 2151 let i1 = ref src1ofs 2152 and i2 = ref src2ofs 2153 and d = ref dstofs 2154 and src1r = src1ofs + src1len 2155 and src2r = src2ofs + src2len 2156 in 2157 while !i1 < src1r && !i2 < src2r do 2158 let s1 = a.(!i1) and s2 = src2.(!i2) in 2159 if cmp s1 s2 <= 0 then begin 2160 dst.(!d) <- s1; 2161 incr i1; 2162 end else begin 2163 dst.(!d) <- s2; 2164 incr i2; 2165 end; 2166 incr d; 2167 done; 2168 if !i1 < src1r then 2169 Array.blit a !i1 dst !d (src1r - !i1) 2170 else 2171 Array.blit src2 !i2 dst !d (src2r - !i2) 2172 in 2173 let isortto srcofs dst dstofs len = 2174 for i = 0 to len-1 do 2175 let e = a.(srcofs+i) in 2176 let j = ref (dstofs+i-1) in 2177 while (!j >= dstofs && cmp dst.(!j) e > 0) do 2178 dst.(!j + 1) <- dst.(!j); 2179 decr j; 2180 done; 2181 dst.(!j + 1) <- e; 2182 done; 2183 in 2184 let rec sortto srcofs dst dstofs len = 2185 if len <= cutoff then isortto srcofs dst dstofs len else 2186 let l1 = len / 2 in 2187 let l2 = len - l1 in 2188 sortto (srcofs+l1) dst (dstofs+l1) l2; 2189 sortto srcofs a (srcofs+l2) l1; 2190 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 2191 in 2192 let l = Array.length a in 2193 if l <= cutoff then isortto 0 a 0 l else begin 2194 let l1 = l / 2 in 2195 let l2 = l - l1 in 2196 let t = Array.make l2 a.(0) in 2197 sortto l1 t 0 l2; 2198 sortto 0 a l2 l1; 2199 merge l2 l1 t 0 l2 a 0; 2200 end; 2201;; 2202 2203let cutoff = 10;; 2204let amerge_3j cmp a = 2205 let merge src1ofs src1len src2 src2ofs src2len dst dstofs = 2206 let i1 = ref src1ofs 2207 and i2 = ref src2ofs 2208 and d = ref dstofs 2209 and src1r = src1ofs + src1len 2210 and src2r = src2ofs + src2len 2211 in 2212 while !i1 < src1r && !i2 < src2r do 2213 let s1 = a.(!i1) and s2 = src2.(!i2) in 2214 if cmp s1 s2 <= 0 then begin 2215 dst.(!d) <- s1; 2216 incr i1; 2217 end else begin 2218 dst.(!d) <- s2; 2219 incr i2; 2220 end; 2221 incr d; 2222 done; 2223 if !i1 < src1r then 2224 Array.blit a !i1 dst !d (src1r - !i1) 2225 else 2226 Array.blit src2 !i2 dst !d (src2r - !i2) 2227 in 2228 let isortto srcofs dst dstofs len = 2229 for i = 0 to len-1 do 2230 let e = a.(srcofs+i) in 2231 let j = ref (dstofs+i-1) in 2232 while (!j >= dstofs && cmp dst.(!j) e > 0) do 2233 dst.(!j + 1) <- dst.(!j); 2234 decr j; 2235 done; 2236 dst.(!j + 1) <- e; 2237 done; 2238 in 2239 let rec sortto srcofs dst dstofs len = 2240 if len <= cutoff then isortto srcofs dst dstofs len else 2241 let l1 = len / 2 in 2242 let l2 = len - l1 in 2243 sortto (srcofs+l1) dst (dstofs+l1) l2; 2244 sortto srcofs a (srcofs+l2) l1; 2245 merge (srcofs+l2) l1 dst (dstofs+l1) l2 dst dstofs; 2246 in 2247 let l = Array.length a in 2248 if l <= cutoff then isortto 0 a 0 l else begin 2249 let l1 = l / 2 in 2250 let l2 = l - l1 in 2251 let t = Array.make l2 a.(0) in 2252 sortto l1 t 0 l2; 2253 sortto 0 a l2 l1; 2254 merge l2 l1 t 0 l2 a 0; 2255 end; 2256;; 2257 2258(* FIXME try bottom-up merge on arrays? *) 2259 2260(************************************************************************) 2261(* Shell sort on arrays *) 2262 2263let ashell_1 cmp a = 2264 let l = Array.length a in 2265 let step = ref 1 in 2266 while !step < l do step := !step * 3 + 1; done; 2267 step := !step / 3; 2268 while !step > 0 do 2269 for j = !step to l-1 do 2270 let e = a.(j) in 2271 let k = ref (j - !step) in 2272 let k1 = ref j in 2273 while !k >= 0 && cmp a.(!k) e > 0 do 2274 a.(!k1) <- a.(!k); 2275 k1 := !k; 2276 k := !k - !step; 2277 done; 2278 a.(!k1) <- e; 2279 done; 2280 step := !step / 3; 2281 done; 2282;; 2283 2284let ashell_2 cmp a = 2285 let l = Array.length a in 2286 let step = ref 1 in 2287 while !step < l do step := !step * 3 + 1; done; 2288 step := !step / 3; 2289 while !step > 0 do 2290 for j = !step to l-1 do 2291 let e = a.(j) in 2292 let k = ref (j - !step) in 2293 while !k >= 0 && cmp a.(!k) e > 0 do 2294 a.(!k + !step) <- a.(!k); 2295 k := !k - !step; 2296 done; 2297 a.(!k + !step) <- e; 2298 done; 2299 step := !step / 3; 2300 done; 2301;; 2302 2303let ashell_3 cmp a = 2304 let l = Array.length a in 2305 let step = ref 1 in 2306 while !step < l do step := !step * 3 + 1; done; 2307 step := !step / 3; 2308 while !step > 0 do 2309 for i = 0 to !step - 1 do 2310 let j = ref (i + !step) in 2311 while !j < l do 2312 let e = ref a.(!j) in 2313 let k = ref (!j - !step) in 2314 if cmp !e a.(i) < 0 then begin 2315 let x = !e in e := a.(i); a.(i) <- x; 2316 end; 2317 while cmp a.(!k) !e > 0 do 2318 a.(!k + !step) <- a.(!k); 2319 k := !k - !step; 2320 done; 2321 a.(!k + !step) <- !e; 2322 j := !j + !step; 2323 done; 2324 done; 2325 step := !step / 3; 2326 done; 2327;; 2328 2329let force = Lazy.force;; 2330 2331type iilist = Cons of int * iilist Lazy.t;; 2332 2333let rec mult n (Cons (x,l)) = Cons (n*x, lazy (mult n (force l))) 2334 2335let rec merge (Cons (x1, t1) as l1) (Cons (x2, t2) as l2) = 2336 if x1 = x2 then Cons (x1, lazy (merge (force t1) (force t2))) 2337 else if x1 < x2 then Cons (x1, lazy (merge (force t1) l2)) 2338 else Cons (x2, lazy (merge l1 (force t2))) 2339;; 2340 2341let rec scale = Cons (1, lazy (merge (mult 2 scale) (mult 3 scale)));; 2342 2343let ashell_4 cmp a = 2344 let l = Array.length a in 2345 let rec loop1 accu (Cons (x, t)) = 2346 if x > l then accu else loop1 (x::accu) (force t) 2347 in 2348 let sc = loop1 [] scale in 2349 let rec loop2 = function 2350 | [] -> () 2351 | step::t -> 2352 for i = 0 to step - 1 do 2353 let j = ref (i + step) in 2354 while !j < l do 2355 let e = a.(!j) in 2356 let k = ref (!j - step) in 2357 while !k >= 0 && cmp a.(!k) e > 0 do 2358 a.(!k + step) <- a.(!k); 2359 k := !k - step; 2360 done; 2361 a.(!k + step) <- e; 2362 j := !j + step; 2363 done; 2364 done; 2365 loop2 t; 2366 in 2367 loop2 sc; 2368;; 2369 2370(************************************************************************) 2371(* Quicksort on arrays *) 2372let cutoff = 1;; 2373let aquick_1a cmp a = 2374 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2375 let m = (l + r) / 2 in 2376 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2377 let pivot = if cmp al am <= 0 then 2378 if cmp am ar <= 0 then am 2379 else if cmp al ar <= 0 then ar 2380 else al 2381 else 2382 if cmp al ar <= 0 then al 2383 else if cmp am ar <= 0 then ar 2384 else am 2385 in 2386 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2387 while !p2 <= !p3 do 2388 let e = a.(!p3) in 2389 let c = cmp e pivot in 2390 if c > 0 then begin 2391 decr p3; 2392 end else if c < 0 then begin 2393 a.(!p3) <- a.(!p2); 2394 a.(!p2) <- a.(!p1); 2395 a.(!p1) <- e; 2396 incr p1; 2397 incr p2; 2398 end else begin 2399 a.(!p3) <- a.(!p2); 2400 a.(!p2) <- e; 2401 incr p2; 2402 end; 2403 done; 2404 incr p3; 2405 let len1 = !p1 - l and len2 = r - !p3 in 2406 if len1 > cutoff then 2407 if len2 > cutoff then begin 2408 if len1 < len2 2409 then (qsort l !p1; qsort !p3 r) 2410 else (qsort !p3 r; qsort l !p1) 2411 end else qsort l !p1 2412 else if len2 > cutoff then qsort !p3 r; 2413 in 2414 let l = Array.length a in 2415 if l > 1 then begin 2416 qsort 0 l; 2417 let mini = ref 0 in 2418 for i = 1 to (min l cutoff) - 1 do 2419 if cmp a.(i) a.(!mini) < 0 then mini := i; 2420 done; 2421 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2422 for i = 1 to l - 1 do 2423 let e = a.(i) in 2424 let j = ref (i - 1) in 2425 while cmp a.(!j) e > 0 do 2426 a.(!j + 1) <- a.(!j); 2427 decr j; 2428 done; 2429 a.(!j + 1) <- e; 2430 done; 2431 end; 2432;; 2433 2434let cutoff = 2;; 2435let aquick_1b cmp a = 2436 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2437 let m = (l + r) / 2 in 2438 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2439 let pivot = if cmp al am <= 0 then 2440 if cmp am ar <= 0 then am 2441 else if cmp al ar <= 0 then ar 2442 else al 2443 else 2444 if cmp al ar <= 0 then al 2445 else if cmp am ar <= 0 then ar 2446 else am 2447 in 2448 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2449 while !p2 <= !p3 do 2450 let e = a.(!p3) in 2451 let c = cmp e pivot in 2452 if c > 0 then begin 2453 decr p3; 2454 end else if c < 0 then begin 2455 a.(!p3) <- a.(!p2); 2456 a.(!p2) <- a.(!p1); 2457 a.(!p1) <- e; 2458 incr p1; 2459 incr p2; 2460 end else begin 2461 a.(!p3) <- a.(!p2); 2462 a.(!p2) <- e; 2463 incr p2; 2464 end; 2465 done; 2466 incr p3; 2467 let len1 = !p1 - l and len2 = r - !p3 in 2468 if len1 > cutoff then 2469 if len2 > cutoff then begin 2470 if len1 < len2 2471 then (qsort l !p1; qsort !p3 r) 2472 else (qsort !p3 r; qsort l !p1) 2473 end else qsort l !p1 2474 else if len2 > cutoff then qsort !p3 r; 2475 in 2476 let l = Array.length a in 2477 if l > 1 then begin 2478 qsort 0 l; 2479 let mini = ref 0 in 2480 for i = 1 to (min l cutoff) - 1 do 2481 if cmp a.(i) a.(!mini) < 0 then mini := i; 2482 done; 2483 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2484 for i = 1 to l - 1 do 2485 let e = a.(i) in 2486 let j = ref (i - 1) in 2487 while cmp a.(!j) e > 0 do 2488 a.(!j + 1) <- a.(!j); 2489 decr j; 2490 done; 2491 a.(!j + 1) <- e; 2492 done; 2493 end; 2494;; 2495 2496let cutoff = 3;; 2497let aquick_1c cmp a = 2498 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2499 let m = (l + r) / 2 in 2500 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2501 let pivot = if cmp al am <= 0 then 2502 if cmp am ar <= 0 then am 2503 else if cmp al ar <= 0 then ar 2504 else al 2505 else 2506 if cmp al ar <= 0 then al 2507 else if cmp am ar <= 0 then ar 2508 else am 2509 in 2510 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2511 while !p2 <= !p3 do 2512 let e = a.(!p3) in 2513 let c = cmp e pivot in 2514 if c > 0 then begin 2515 decr p3; 2516 end else if c < 0 then begin 2517 a.(!p3) <- a.(!p2); 2518 a.(!p2) <- a.(!p1); 2519 a.(!p1) <- e; 2520 incr p1; 2521 incr p2; 2522 end else begin 2523 a.(!p3) <- a.(!p2); 2524 a.(!p2) <- e; 2525 incr p2; 2526 end; 2527 done; 2528 incr p3; 2529 let len1 = !p1 - l and len2 = r - !p3 in 2530 if len1 > cutoff then 2531 if len2 > cutoff then begin 2532 if len1 < len2 2533 then (qsort l !p1; qsort !p3 r) 2534 else (qsort !p3 r; qsort l !p1) 2535 end else qsort l !p1 2536 else if len2 > cutoff then qsort !p3 r; 2537 in 2538 let l = Array.length a in 2539 if l > 1 then begin 2540 qsort 0 l; 2541 let mini = ref 0 in 2542 for i = 1 to (min l cutoff) - 1 do 2543 if cmp a.(i) a.(!mini) < 0 then mini := i; 2544 done; 2545 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2546 for i = 1 to l - 1 do 2547 let e = a.(i) in 2548 let j = ref (i - 1) in 2549 while cmp a.(!j) e > 0 do 2550 a.(!j + 1) <- a.(!j); 2551 decr j; 2552 done; 2553 a.(!j + 1) <- e; 2554 done; 2555 end; 2556;; 2557 2558let cutoff = 4;; 2559let aquick_1d cmp a = 2560 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2561 let m = (l + r) / 2 in 2562 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2563 let pivot = if cmp al am <= 0 then 2564 if cmp am ar <= 0 then am 2565 else if cmp al ar <= 0 then ar 2566 else al 2567 else 2568 if cmp al ar <= 0 then al 2569 else if cmp am ar <= 0 then ar 2570 else am 2571 in 2572 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2573 while !p2 <= !p3 do 2574 let e = a.(!p3) in 2575 let c = cmp e pivot in 2576 if c > 0 then begin 2577 decr p3; 2578 end else if c < 0 then begin 2579 a.(!p3) <- a.(!p2); 2580 a.(!p2) <- a.(!p1); 2581 a.(!p1) <- e; 2582 incr p1; 2583 incr p2; 2584 end else begin 2585 a.(!p3) <- a.(!p2); 2586 a.(!p2) <- e; 2587 incr p2; 2588 end; 2589 done; 2590 incr p3; 2591 let len1 = !p1 - l and len2 = r - !p3 in 2592 if len1 > cutoff then 2593 if len2 > cutoff then begin 2594 if len1 < len2 2595 then (qsort l !p1; qsort !p3 r) 2596 else (qsort !p3 r; qsort l !p1) 2597 end else qsort l !p1 2598 else if len2 > cutoff then qsort !p3 r; 2599 in 2600 let l = Array.length a in 2601 if l > 1 then begin 2602 qsort 0 l; 2603 let mini = ref 0 in 2604 for i = 1 to (min l cutoff) - 1 do 2605 if cmp a.(i) a.(!mini) < 0 then mini := i; 2606 done; 2607 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2608 for i = 1 to l - 1 do 2609 let e = a.(i) in 2610 let j = ref (i - 1) in 2611 while cmp a.(!j) e > 0 do 2612 a.(!j + 1) <- a.(!j); 2613 decr j; 2614 done; 2615 a.(!j + 1) <- e; 2616 done; 2617 end; 2618;; 2619 2620let cutoff = 5;; 2621let aquick_1e cmp a = 2622 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2623 let m = (l + r) / 2 in 2624 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2625 let pivot = if cmp al am <= 0 then 2626 if cmp am ar <= 0 then am 2627 else if cmp al ar <= 0 then ar 2628 else al 2629 else 2630 if cmp al ar <= 0 then al 2631 else if cmp am ar <= 0 then ar 2632 else am 2633 in 2634 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2635 while !p2 <= !p3 do 2636 let e = a.(!p3) in 2637 let c = cmp e pivot in 2638 if c > 0 then begin 2639 decr p3; 2640 end else if c < 0 then begin 2641 a.(!p3) <- a.(!p2); 2642 a.(!p2) <- a.(!p1); 2643 a.(!p1) <- e; 2644 incr p1; 2645 incr p2; 2646 end else begin 2647 a.(!p3) <- a.(!p2); 2648 a.(!p2) <- e; 2649 incr p2; 2650 end; 2651 done; 2652 incr p3; 2653 let len1 = !p1 - l and len2 = r - !p3 in 2654 if len1 > cutoff then 2655 if len2 > cutoff then begin 2656 if len1 < len2 2657 then (qsort l !p1; qsort !p3 r) 2658 else (qsort !p3 r; qsort l !p1) 2659 end else qsort l !p1 2660 else if len2 > cutoff then qsort !p3 r; 2661 in 2662 let l = Array.length a in 2663 if l > 1 then begin 2664 qsort 0 l; 2665 let mini = ref 0 in 2666 for i = 1 to (min l cutoff) - 1 do 2667 if cmp a.(i) a.(!mini) < 0 then mini := i; 2668 done; 2669 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2670 for i = 1 to l - 1 do 2671 let e = a.(i) in 2672 let j = ref (i - 1) in 2673 while cmp a.(!j) e > 0 do 2674 a.(!j + 1) <- a.(!j); 2675 decr j; 2676 done; 2677 a.(!j + 1) <- e; 2678 done; 2679 end; 2680;; 2681 2682let cutoff = 6;; 2683let aquick_1f cmp a = 2684 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2685 let m = (l + r) / 2 in 2686 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2687 let pivot = if cmp al am <= 0 then 2688 if cmp am ar <= 0 then am 2689 else if cmp al ar <= 0 then ar 2690 else al 2691 else 2692 if cmp al ar <= 0 then al 2693 else if cmp am ar <= 0 then ar 2694 else am 2695 in 2696 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2697 while !p2 <= !p3 do 2698 let e = a.(!p3) in 2699 let c = cmp e pivot in 2700 if c > 0 then begin 2701 decr p3; 2702 end else if c < 0 then begin 2703 a.(!p3) <- a.(!p2); 2704 a.(!p2) <- a.(!p1); 2705 a.(!p1) <- e; 2706 incr p1; 2707 incr p2; 2708 end else begin 2709 a.(!p3) <- a.(!p2); 2710 a.(!p2) <- e; 2711 incr p2; 2712 end; 2713 done; 2714 incr p3; 2715 let len1 = !p1 - l and len2 = r - !p3 in 2716 if len1 > cutoff then 2717 if len2 > cutoff then begin 2718 if len1 < len2 2719 then (qsort l !p1; qsort !p3 r) 2720 else (qsort !p3 r; qsort l !p1) 2721 end else qsort l !p1 2722 else if len2 > cutoff then qsort !p3 r; 2723 in 2724 let l = Array.length a in 2725 if l > 1 then begin 2726 qsort 0 l; 2727 let mini = ref 0 in 2728 for i = 1 to (min l cutoff) - 1 do 2729 if cmp a.(i) a.(!mini) < 0 then mini := i; 2730 done; 2731 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2732 for i = 1 to l - 1 do 2733 let e = a.(i) in 2734 let j = ref (i - 1) in 2735 while cmp a.(!j) e > 0 do 2736 a.(!j + 1) <- a.(!j); 2737 decr j; 2738 done; 2739 a.(!j + 1) <- e; 2740 done; 2741 end; 2742;; 2743 2744let cutoff = 7;; 2745let aquick_1g cmp a = 2746 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2747 let m = (l + r) / 2 in 2748 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2749 let pivot = if cmp al am <= 0 then 2750 if cmp am ar <= 0 then am 2751 else if cmp al ar <= 0 then ar 2752 else al 2753 else 2754 if cmp al ar <= 0 then al 2755 else if cmp am ar <= 0 then ar 2756 else am 2757 in 2758 let p1 = ref l and p2 = ref l and p3 = ref (r - 1) in 2759 while !p2 <= !p3 do 2760 let e = a.(!p3) in 2761 let c = cmp e pivot in 2762 if c > 0 then begin 2763 decr p3; 2764 end else if c < 0 then begin 2765 a.(!p3) <- a.(!p2); 2766 a.(!p2) <- a.(!p1); 2767 a.(!p1) <- e; 2768 incr p1; 2769 incr p2; 2770 end else begin 2771 a.(!p3) <- a.(!p2); 2772 a.(!p2) <- e; 2773 incr p2; 2774 end; 2775 done; 2776 incr p3; 2777 let len1 = !p1 - l and len2 = r - !p3 in 2778 if len1 > cutoff then 2779 if len2 > cutoff then begin 2780 if len1 < len2 2781 then (qsort l !p1; qsort !p3 r) 2782 else (qsort !p3 r; qsort l !p1) 2783 end else qsort l !p1 2784 else if len2 > cutoff then qsort !p3 r; 2785 in 2786 let l = Array.length a in 2787 if l > 1 then begin 2788 qsort 0 l; 2789 let mini = ref 0 in 2790 for i = 1 to (min l cutoff) - 1 do 2791 if cmp a.(i) a.(!mini) < 0 then mini := i; 2792 done; 2793 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2794 for i = 1 to l - 1 do 2795 let e = a.(i) in 2796 let j = ref (i - 1) in 2797 while cmp a.(!j) e > 0 do 2798 a.(!j + 1) <- a.(!j); 2799 decr j; 2800 done; 2801 a.(!j + 1) <- e; 2802 done; 2803 end; 2804;; 2805 2806let cutoff = 1;; 2807let aquick_2a cmp a = 2808 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2809 let m = (l + r) / 2 in 2810 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2811 let pivot = if cmp al am <= 0 then 2812 if cmp am ar <= 0 then am 2813 else if cmp al ar <= 0 then ar 2814 else al 2815 else 2816 if cmp al ar <= 0 then al 2817 else if cmp am ar <= 0 then ar 2818 else am 2819 in 2820 let p1 = ref l and p2 = ref l and p3 = ref r in 2821 while !p2 < !p3 do 2822 let e = a.(!p2) in 2823 let c = cmp e pivot in 2824 if c > 0 then begin 2825 decr p3; 2826 a.(!p2) <- a.(!p3); 2827 a.(!p3) <- e; 2828 end else if c < 0 then begin 2829 a.(!p2) <- a.(!p1); 2830 a.(!p1) <- e; 2831 incr p1; 2832 incr p2; 2833 end else begin 2834 incr p2; 2835 end; 2836 done; 2837 let len1 = !p1 - l and len2 = r - !p3 in 2838 if len1 > cutoff then 2839 if len2 > cutoff then begin 2840 if len1 < len2 2841 then (qsort l !p1; qsort !p3 r) 2842 else (qsort !p3 r; qsort l !p1) 2843 end else qsort l !p1 2844 else if len2 > cutoff then qsort !p3 r; 2845 in 2846 let l = Array.length a in 2847 if l > 1 then begin 2848 qsort 0 l; 2849 let mini = ref 0 in 2850 for i = 0 to (min l cutoff) - 1 do 2851 if cmp a.(i) a.(!mini) < 0 then mini := i; 2852 done; 2853 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2854 for i = 1 to l - 1 do 2855 let e = a.(i) in 2856 let j = ref (i - 1) in 2857 while cmp a.(!j) e > 0 do 2858 a.(!j + 1) <- a.(!j); 2859 decr j; 2860 done; 2861 a.(!j + 1) <- e; 2862 done; 2863 end; 2864;; 2865 2866let cutoff = 2;; 2867let aquick_2b cmp a = 2868 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2869 let m = (l + r) / 2 in 2870 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2871 let pivot = if cmp al am <= 0 then 2872 if cmp am ar <= 0 then am 2873 else if cmp al ar <= 0 then ar 2874 else al 2875 else 2876 if cmp al ar <= 0 then al 2877 else if cmp am ar <= 0 then ar 2878 else am 2879 in 2880 let p1 = ref l and p2 = ref l and p3 = ref r in 2881 while !p2 < !p3 do 2882 let e = a.(!p2) in 2883 let c = cmp e pivot in 2884 if c > 0 then begin 2885 decr p3; 2886 a.(!p2) <- a.(!p3); 2887 a.(!p3) <- e; 2888 end else if c < 0 then begin 2889 a.(!p2) <- a.(!p1); 2890 a.(!p1) <- e; 2891 incr p1; 2892 incr p2; 2893 end else begin 2894 incr p2; 2895 end; 2896 done; 2897 let len1 = !p1 - l and len2 = r - !p3 in 2898 if len1 > cutoff then 2899 if len2 > cutoff then begin 2900 if len1 < len2 2901 then (qsort l !p1; qsort !p3 r) 2902 else (qsort !p3 r; qsort l !p1) 2903 end else qsort l !p1 2904 else if len2 > cutoff then qsort !p3 r; 2905 in 2906 let l = Array.length a in 2907 if l > 1 then begin 2908 qsort 0 l; 2909 let mini = ref 0 in 2910 for i = 0 to (min l cutoff) - 1 do 2911 if cmp a.(i) a.(!mini) < 0 then mini := i; 2912 done; 2913 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2914 for i = 1 to l - 1 do 2915 let e = a.(i) in 2916 let j = ref (i - 1) in 2917 while cmp a.(!j) e > 0 do 2918 a.(!j + 1) <- a.(!j); 2919 decr j; 2920 done; 2921 a.(!j + 1) <- e; 2922 done; 2923 end; 2924;; 2925 2926let cutoff = 3;; 2927let aquick_2c cmp a = 2928 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2929 let m = (l + r) / 2 in 2930 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2931 let pivot = if cmp al am <= 0 then 2932 if cmp am ar <= 0 then am 2933 else if cmp al ar <= 0 then ar 2934 else al 2935 else 2936 if cmp al ar <= 0 then al 2937 else if cmp am ar <= 0 then ar 2938 else am 2939 in 2940 let p1 = ref l and p2 = ref l and p3 = ref r in 2941 while !p2 < !p3 do 2942 let e = a.(!p2) in 2943 let c = cmp e pivot in 2944 if c > 0 then begin 2945 decr p3; 2946 a.(!p2) <- a.(!p3); 2947 a.(!p3) <- e; 2948 end else if c < 0 then begin 2949 a.(!p2) <- a.(!p1); 2950 a.(!p1) <- e; 2951 incr p1; 2952 incr p2; 2953 end else begin 2954 incr p2; 2955 end; 2956 done; 2957 let len1 = !p1 - l and len2 = r - !p3 in 2958 if len1 > cutoff then 2959 if len2 > cutoff then begin 2960 if len1 < len2 2961 then (qsort l !p1; qsort !p3 r) 2962 else (qsort !p3 r; qsort l !p1) 2963 end else qsort l !p1 2964 else if len2 > cutoff then qsort !p3 r; 2965 in 2966 let l = Array.length a in 2967 if l > 1 then begin 2968 qsort 0 l; 2969 let mini = ref 0 in 2970 for i = 0 to (min l cutoff) - 1 do 2971 if cmp a.(i) a.(!mini) < 0 then mini := i; 2972 done; 2973 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 2974 for i = 1 to l - 1 do 2975 let e = a.(i) in 2976 let j = ref (i - 1) in 2977 while cmp a.(!j) e > 0 do 2978 a.(!j + 1) <- a.(!j); 2979 decr j; 2980 done; 2981 a.(!j + 1) <- e; 2982 done; 2983 end; 2984;; 2985 2986let cutoff = 4;; 2987let aquick_2d cmp a = 2988 let rec qsort l r = (* ASSUMES r - l >= 2 *) 2989 let m = (l + r) / 2 in 2990 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 2991 let pivot = if cmp al am <= 0 then 2992 if cmp am ar <= 0 then am 2993 else if cmp al ar <= 0 then ar 2994 else al 2995 else 2996 if cmp al ar <= 0 then al 2997 else if cmp am ar <= 0 then ar 2998 else am 2999 in 3000 let p1 = ref l and p2 = ref l and p3 = ref r in 3001 while !p2 < !p3 do 3002 let e = a.(!p2) in 3003 let c = cmp e pivot in 3004 if c > 0 then begin 3005 decr p3; 3006 a.(!p2) <- a.(!p3); 3007 a.(!p3) <- e; 3008 end else if c < 0 then begin 3009 a.(!p2) <- a.(!p1); 3010 a.(!p1) <- e; 3011 incr p1; 3012 incr p2; 3013 end else begin 3014 incr p2; 3015 end; 3016 done; 3017 let len1 = !p1 - l and len2 = r - !p3 in 3018 if len1 > cutoff then 3019 if len2 > cutoff then begin 3020 if len1 < len2 3021 then (qsort l !p1; qsort !p3 r) 3022 else (qsort !p3 r; qsort l !p1) 3023 end else qsort l !p1 3024 else if len2 > cutoff then qsort !p3 r; 3025 in 3026 let l = Array.length a in 3027 if l > 1 then begin 3028 qsort 0 l; 3029 let mini = ref 0 in 3030 for i = 0 to (min l cutoff) - 1 do 3031 if cmp a.(i) a.(!mini) < 0 then mini := i; 3032 done; 3033 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3034 for i = 1 to l - 1 do 3035 let e = a.(i) in 3036 let j = ref (i - 1) in 3037 while cmp a.(!j) e > 0 do 3038 a.(!j + 1) <- a.(!j); 3039 decr j; 3040 done; 3041 a.(!j + 1) <- e; 3042 done; 3043 end; 3044;; 3045 3046let cutoff = 5;; 3047let aquick_2e cmp a = 3048 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3049 let m = (l + r) / 2 in 3050 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3051 let pivot = if cmp al am <= 0 then 3052 if cmp am ar <= 0 then am 3053 else if cmp al ar <= 0 then ar 3054 else al 3055 else 3056 if cmp al ar <= 0 then al 3057 else if cmp am ar <= 0 then ar 3058 else am 3059 in 3060 let p1 = ref l and p2 = ref l and p3 = ref r in 3061 while !p2 < !p3 do 3062 let e = a.(!p2) in 3063 let c = cmp e pivot in 3064 if c > 0 then begin 3065 decr p3; 3066 a.(!p2) <- a.(!p3); 3067 a.(!p3) <- e; 3068 end else if c < 0 then begin 3069 a.(!p2) <- a.(!p1); 3070 a.(!p1) <- e; 3071 incr p1; 3072 incr p2; 3073 end else begin 3074 incr p2; 3075 end; 3076 done; 3077 let len1 = !p1 - l and len2 = r - !p3 in 3078 if len1 > cutoff then 3079 if len2 > cutoff then begin 3080 if len1 < len2 3081 then (qsort l !p1; qsort !p3 r) 3082 else (qsort !p3 r; qsort l !p1) 3083 end else qsort l !p1 3084 else if len2 > cutoff then qsort !p3 r; 3085 in 3086 let l = Array.length a in 3087 if l > 1 then begin 3088 qsort 0 l; 3089 let mini = ref 0 in 3090 for i = 0 to (min l cutoff) - 1 do 3091 if cmp a.(i) a.(!mini) < 0 then mini := i; 3092 done; 3093 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3094 for i = 1 to l - 1 do 3095 let e = a.(i) in 3096 let j = ref (i - 1) in 3097 while cmp a.(!j) e > 0 do 3098 a.(!j + 1) <- a.(!j); 3099 decr j; 3100 done; 3101 a.(!j + 1) <- e; 3102 done; 3103 end; 3104;; 3105 3106let cutoff = 6;; 3107let aquick_2f cmp a = 3108 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3109 let m = (l + r) / 2 in 3110 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3111 let pivot = if cmp al am <= 0 then 3112 if cmp am ar <= 0 then am 3113 else if cmp al ar <= 0 then ar 3114 else al 3115 else 3116 if cmp al ar <= 0 then al 3117 else if cmp am ar <= 0 then ar 3118 else am 3119 in 3120 let p1 = ref l and p2 = ref l and p3 = ref r in 3121 while !p2 < !p3 do 3122 let e = a.(!p2) in 3123 let c = cmp e pivot in 3124 if c > 0 then begin 3125 decr p3; 3126 a.(!p2) <- a.(!p3); 3127 a.(!p3) <- e; 3128 end else if c < 0 then begin 3129 a.(!p2) <- a.(!p1); 3130 a.(!p1) <- e; 3131 incr p1; 3132 incr p2; 3133 end else begin 3134 incr p2; 3135 end; 3136 done; 3137 let len1 = !p1 - l and len2 = r - !p3 in 3138 if len1 > cutoff then 3139 if len2 > cutoff then begin 3140 if len1 < len2 3141 then (qsort l !p1; qsort !p3 r) 3142 else (qsort !p3 r; qsort l !p1) 3143 end else qsort l !p1 3144 else if len2 > cutoff then qsort !p3 r; 3145 in 3146 let l = Array.length a in 3147 if l > 1 then begin 3148 qsort 0 l; 3149 let mini = ref 0 in 3150 for i = 0 to (min l cutoff) - 1 do 3151 if cmp a.(i) a.(!mini) < 0 then mini := i; 3152 done; 3153 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3154 for i = 1 to l - 1 do 3155 let e = a.(i) in 3156 let j = ref (i - 1) in 3157 while cmp a.(!j) e > 0 do 3158 a.(!j + 1) <- a.(!j); 3159 decr j; 3160 done; 3161 a.(!j + 1) <- e; 3162 done; 3163 end; 3164;; 3165 3166let cutoff = 7;; 3167let aquick_2g cmp a = 3168 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3169 let m = (l + r) / 2 in 3170 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3171 let pivot = if cmp al am <= 0 then 3172 if cmp am ar <= 0 then am 3173 else if cmp al ar <= 0 then ar 3174 else al 3175 else 3176 if cmp al ar <= 0 then al 3177 else if cmp am ar <= 0 then ar 3178 else am 3179 in 3180 let p1 = ref l and p2 = ref l and p3 = ref r in 3181 while !p2 < !p3 do 3182 let e = a.(!p2) in 3183 let c = cmp e pivot in 3184 if c > 0 then begin 3185 decr p3; 3186 a.(!p2) <- a.(!p3); 3187 a.(!p3) <- e; 3188 end else if c < 0 then begin 3189 a.(!p2) <- a.(!p1); 3190 a.(!p1) <- e; 3191 incr p1; 3192 incr p2; 3193 end else begin 3194 incr p2; 3195 end; 3196 done; 3197 let len1 = !p1 - l and len2 = r - !p3 in 3198 if len1 > cutoff then 3199 if len2 > cutoff then begin 3200 if len1 < len2 3201 then (qsort l !p1; qsort !p3 r) 3202 else (qsort !p3 r; qsort l !p1) 3203 end else qsort l !p1 3204 else if len2 > cutoff then qsort !p3 r; 3205 in 3206 let l = Array.length a in 3207 if l > 1 then begin 3208 qsort 0 l; 3209 let mini = ref 0 in 3210 for i = 0 to (min l cutoff) - 1 do 3211 if cmp a.(i) a.(!mini) < 0 then mini := i; 3212 done; 3213 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3214 for i = 1 to l - 1 do 3215 let e = a.(i) in 3216 let j = ref (i - 1) in 3217 while cmp a.(!j) e > 0 do 3218 a.(!j + 1) <- a.(!j); 3219 decr j; 3220 done; 3221 a.(!j + 1) <- e; 3222 done; 3223 end; 3224;; 3225 3226let cutoff = 1;; 3227let aquick_3a cmp a = 3228 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3229 let m = (l + r) / 2 in 3230 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3231 let pivot = if cmp al am <= 0 then 3232 if cmp am ar <= 0 then am 3233 else if cmp al ar <= 0 then ar 3234 else al 3235 else 3236 if cmp al ar <= 0 then al 3237 else if cmp am ar <= 0 then ar 3238 else am 3239 in 3240 let p1 = ref l and p2 = ref l and p3 = ref r in 3241 while !p2 < !p3 do 3242 let e = a.(!p2) in 3243 let c = cmp e pivot in 3244 if c > 0 then begin 3245 decr p3; 3246 a.(!p2) <- a.(!p3); 3247 a.(!p3) <- e; 3248 end else if c < 0 then begin 3249 incr p2; 3250 end else begin 3251 a.(!p2) <- a.(!p1); 3252 a.(!p1) <- e; 3253 incr p1; 3254 incr p2; 3255 end 3256 done; 3257 while !p1 > l do 3258 decr p1; 3259 decr p2; 3260 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3261 done; 3262 let len1 = !p2 - l and len2 = r - !p3 in 3263 if len1 > cutoff then 3264 if len2 > cutoff then begin 3265 if len1 < len2 3266 then (qsort l !p2; qsort !p3 r) 3267 else (qsort !p3 r; qsort l !p2) 3268 end else qsort l !p2 3269 else if len2 > cutoff then qsort !p3 r; 3270 in 3271 let l = Array.length a in 3272 if l > 1 then begin 3273 qsort 0 l; 3274 let mini = ref 0 in 3275 for i = 0 to (min l cutoff) - 1 do 3276 if cmp a.(i) a.(!mini) < 0 then mini := i; 3277 done; 3278 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3279 for i = 1 to l - 1 do 3280 let e = a.(i) in 3281 let j = ref (i - 1) in 3282 while cmp a.(!j) e > 0 do 3283 a.(!j + 1) <- a.(!j); 3284 decr j; 3285 done; 3286 a.(!j + 1) <- e; 3287 done; 3288 end; 3289;; 3290 3291let cutoff = 2;; 3292let aquick_3b cmp a = 3293 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3294 let m = (l + r) / 2 in 3295 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3296 let pivot = if cmp al am <= 0 then 3297 if cmp am ar <= 0 then am 3298 else if cmp al ar <= 0 then ar 3299 else al 3300 else 3301 if cmp al ar <= 0 then al 3302 else if cmp am ar <= 0 then ar 3303 else am 3304 in 3305 let p1 = ref l and p2 = ref l and p3 = ref r in 3306 while !p2 < !p3 do 3307 let e = a.(!p2) in 3308 let c = cmp e pivot in 3309 if c > 0 then begin 3310 decr p3; 3311 a.(!p2) <- a.(!p3); 3312 a.(!p3) <- e; 3313 end else if c < 0 then begin 3314 incr p2; 3315 end else begin 3316 a.(!p2) <- a.(!p1); 3317 a.(!p1) <- e; 3318 incr p1; 3319 incr p2; 3320 end 3321 done; 3322 while !p1 > l do 3323 decr p1; 3324 decr p2; 3325 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3326 done; 3327 let len1 = !p2 - l and len2 = r - !p3 in 3328 if len1 > cutoff then 3329 if len2 > cutoff then begin 3330 if len1 < len2 3331 then (qsort l !p2; qsort !p3 r) 3332 else (qsort !p3 r; qsort l !p2) 3333 end else qsort l !p2 3334 else if len2 > cutoff then qsort !p3 r; 3335 in 3336 let l = Array.length a in 3337 if l > 1 then begin 3338 qsort 0 l; 3339 let mini = ref 0 in 3340 for i = 0 to (min l cutoff) - 1 do 3341 if cmp a.(i) a.(!mini) < 0 then mini := i; 3342 done; 3343 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3344 for i = 1 to l - 1 do 3345 let e = a.(i) in 3346 let j = ref (i - 1) in 3347 while cmp a.(!j) e > 0 do 3348 a.(!j + 1) <- a.(!j); 3349 decr j; 3350 done; 3351 a.(!j + 1) <- e; 3352 done; 3353 end; 3354;; 3355 3356let cutoff = 3;; 3357let aquick_3c cmp a = 3358 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3359 let m = (l + r) / 2 in 3360 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3361 let pivot = if cmp al am <= 0 then 3362 if cmp am ar <= 0 then am 3363 else if cmp al ar <= 0 then ar 3364 else al 3365 else 3366 if cmp al ar <= 0 then al 3367 else if cmp am ar <= 0 then ar 3368 else am 3369 in 3370 let p1 = ref l and p2 = ref l and p3 = ref r in 3371 while !p2 < !p3 do 3372 let e = a.(!p2) in 3373 let c = cmp e pivot in 3374 if c > 0 then begin 3375 decr p3; 3376 a.(!p2) <- a.(!p3); 3377 a.(!p3) <- e; 3378 end else if c < 0 then begin 3379 incr p2; 3380 end else begin 3381 a.(!p2) <- a.(!p1); 3382 a.(!p1) <- e; 3383 incr p1; 3384 incr p2; 3385 end 3386 done; 3387 while !p1 > l do 3388 decr p1; 3389 decr p2; 3390 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3391 done; 3392 let len1 = !p2 - l and len2 = r - !p3 in 3393 if len1 > cutoff then 3394 if len2 > cutoff then begin 3395 if len1 < len2 3396 then (qsort l !p2; qsort !p3 r) 3397 else (qsort !p3 r; qsort l !p2) 3398 end else qsort l !p2 3399 else if len2 > cutoff then qsort !p3 r; 3400 in 3401 let l = Array.length a in 3402 if l > 1 then begin 3403 qsort 0 l; 3404 let mini = ref 0 in 3405 for i = 0 to (min l cutoff) - 1 do 3406 if cmp a.(i) a.(!mini) < 0 then mini := i; 3407 done; 3408 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3409 for i = 1 to l - 1 do 3410 let e = a.(i) in 3411 let j = ref (i - 1) in 3412 while cmp a.(!j) e > 0 do 3413 a.(!j + 1) <- a.(!j); 3414 decr j; 3415 done; 3416 a.(!j + 1) <- e; 3417 done; 3418 end; 3419;; 3420 3421let cutoff = 4;; 3422let aquick_3d cmp a = 3423 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3424 let m = (l + r) / 2 in 3425 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3426 let pivot = if cmp al am <= 0 then 3427 if cmp am ar <= 0 then am 3428 else if cmp al ar <= 0 then ar 3429 else al 3430 else 3431 if cmp al ar <= 0 then al 3432 else if cmp am ar <= 0 then ar 3433 else am 3434 in 3435 let p1 = ref l and p2 = ref l and p3 = ref r in 3436 while !p2 < !p3 do 3437 let e = a.(!p2) in 3438 let c = cmp e pivot in 3439 if c > 0 then begin 3440 decr p3; 3441 a.(!p2) <- a.(!p3); 3442 a.(!p3) <- e; 3443 end else if c < 0 then begin 3444 incr p2; 3445 end else begin 3446 a.(!p2) <- a.(!p1); 3447 a.(!p1) <- e; 3448 incr p1; 3449 incr p2; 3450 end 3451 done; 3452 while !p1 > l do 3453 decr p1; 3454 decr p2; 3455 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3456 done; 3457 let len1 = !p2 - l and len2 = r - !p3 in 3458 if len1 > cutoff then 3459 if len2 > cutoff then begin 3460 if len1 < len2 3461 then (qsort l !p2; qsort !p3 r) 3462 else (qsort !p3 r; qsort l !p2) 3463 end else qsort l !p2 3464 else if len2 > cutoff then qsort !p3 r; 3465 in 3466 let l = Array.length a in 3467 if l > 1 then begin 3468 qsort 0 l; 3469 let mini = ref 0 in 3470 for i = 0 to (min l cutoff) - 1 do 3471 if cmp a.(i) a.(!mini) < 0 then mini := i; 3472 done; 3473 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3474 for i = 1 to l - 1 do 3475 let e = a.(i) in 3476 let j = ref (i - 1) in 3477 while cmp a.(!j) e > 0 do 3478 a.(!j + 1) <- a.(!j); 3479 decr j; 3480 done; 3481 a.(!j + 1) <- e; 3482 done; 3483 end; 3484;; 3485 3486let cutoff = 5;; 3487let aquick_3e cmp a = 3488 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3489 let m = (l + r) / 2 in 3490 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3491 let pivot = if cmp al am <= 0 then 3492 if cmp am ar <= 0 then am 3493 else if cmp al ar <= 0 then ar 3494 else al 3495 else 3496 if cmp al ar <= 0 then al 3497 else if cmp am ar <= 0 then ar 3498 else am 3499 in 3500 let p1 = ref l and p2 = ref l and p3 = ref r in 3501 while !p2 < !p3 do 3502 let e = a.(!p2) in 3503 let c = cmp e pivot in 3504 if c > 0 then begin 3505 decr p3; 3506 a.(!p2) <- a.(!p3); 3507 a.(!p3) <- e; 3508 end else if c < 0 then begin 3509 incr p2; 3510 end else begin 3511 a.(!p2) <- a.(!p1); 3512 a.(!p1) <- e; 3513 incr p1; 3514 incr p2; 3515 end 3516 done; 3517 while !p1 > l do 3518 decr p1; 3519 decr p2; 3520 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3521 done; 3522 let len1 = !p2 - l and len2 = r - !p3 in 3523 if len1 > cutoff then 3524 if len2 > cutoff then begin 3525 if len1 < len2 3526 then (qsort l !p2; qsort !p3 r) 3527 else (qsort !p3 r; qsort l !p2) 3528 end else qsort l !p2 3529 else if len2 > cutoff then qsort !p3 r; 3530 in 3531 let l = Array.length a in 3532 if l > 1 then begin 3533 qsort 0 l; 3534 let mini = ref 0 in 3535 for i = 0 to (min l cutoff) - 1 do 3536 if cmp a.(i) a.(!mini) < 0 then mini := i; 3537 done; 3538 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3539 for i = 1 to l - 1 do 3540 let e = a.(i) in 3541 let j = ref (i - 1) in 3542 while cmp a.(!j) e > 0 do 3543 a.(!j + 1) <- a.(!j); 3544 decr j; 3545 done; 3546 a.(!j + 1) <- e; 3547 done; 3548 end; 3549;; 3550 3551let cutoff = 6;; 3552let aquick_3f cmp a = 3553 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3554 let m = (l + r) / 2 in 3555 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3556 let pivot = if cmp al am <= 0 then 3557 if cmp am ar <= 0 then am 3558 else if cmp al ar <= 0 then ar 3559 else al 3560 else 3561 if cmp al ar <= 0 then al 3562 else if cmp am ar <= 0 then ar 3563 else am 3564 in 3565 let p1 = ref l and p2 = ref l and p3 = ref r in 3566 while !p2 < !p3 do 3567 let e = a.(!p2) in 3568 let c = cmp e pivot in 3569 if c > 0 then begin 3570 decr p3; 3571 a.(!p2) <- a.(!p3); 3572 a.(!p3) <- e; 3573 end else if c < 0 then begin 3574 incr p2; 3575 end else begin 3576 a.(!p2) <- a.(!p1); 3577 a.(!p1) <- e; 3578 incr p1; 3579 incr p2; 3580 end 3581 done; 3582 while !p1 > l do 3583 decr p1; 3584 decr p2; 3585 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3586 done; 3587 let len1 = !p2 - l and len2 = r - !p3 in 3588 if len1 > cutoff then 3589 if len2 > cutoff then begin 3590 if len1 < len2 3591 then (qsort l !p2; qsort !p3 r) 3592 else (qsort !p3 r; qsort l !p2) 3593 end else qsort l !p2 3594 else if len2 > cutoff then qsort !p3 r; 3595 in 3596 let l = Array.length a in 3597 if l > 1 then begin 3598 qsort 0 l; 3599 let mini = ref 0 in 3600 for i = 0 to (min l cutoff) - 1 do 3601 if cmp a.(i) a.(!mini) < 0 then mini := i; 3602 done; 3603 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3604 for i = 1 to l - 1 do 3605 let e = a.(i) in 3606 let j = ref (i - 1) in 3607 while cmp a.(!j) e > 0 do 3608 a.(!j + 1) <- a.(!j); 3609 decr j; 3610 done; 3611 a.(!j + 1) <- e; 3612 done; 3613 end; 3614;; 3615 3616let cutoff = 7;; 3617let aquick_3g cmp a = 3618 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3619 let m = (l + r) / 2 in 3620 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3621 let pivot = if cmp al am <= 0 then 3622 if cmp am ar <= 0 then am 3623 else if cmp al ar <= 0 then ar 3624 else al 3625 else 3626 if cmp al ar <= 0 then al 3627 else if cmp am ar <= 0 then ar 3628 else am 3629 in 3630 let p1 = ref l and p2 = ref l and p3 = ref r in 3631 while !p2 < !p3 do 3632 let e = a.(!p2) in 3633 let c = cmp e pivot in 3634 if c > 0 then begin 3635 decr p3; 3636 a.(!p2) <- a.(!p3); 3637 a.(!p3) <- e; 3638 end else if c < 0 then begin 3639 incr p2; 3640 end else begin 3641 a.(!p2) <- a.(!p1); 3642 a.(!p1) <- e; 3643 incr p1; 3644 incr p2; 3645 end 3646 done; 3647 while !p1 > l do 3648 decr p1; 3649 decr p2; 3650 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3651 done; 3652 let len1 = !p2 - l and len2 = r - !p3 in 3653 if len1 > cutoff then 3654 if len2 > cutoff then begin 3655 if len1 < len2 3656 then (qsort l !p2; qsort !p3 r) 3657 else (qsort !p3 r; qsort l !p2) 3658 end else qsort l !p2 3659 else if len2 > cutoff then qsort !p3 r; 3660 in 3661 let l = Array.length a in 3662 if l > 1 then begin 3663 qsort 0 l; 3664 let mini = ref 0 in 3665 for i = 0 to (min l cutoff) - 1 do 3666 if cmp a.(i) a.(!mini) < 0 then mini := i; 3667 done; 3668 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3669 for i = 1 to l - 1 do 3670 let e = a.(i) in 3671 let j = ref (i - 1) in 3672 while cmp a.(!j) e > 0 do 3673 a.(!j + 1) <- a.(!j); 3674 decr j; 3675 done; 3676 a.(!j + 1) <- e; 3677 done; 3678 end; 3679;; 3680 3681let cutoff = 8;; 3682let aquick_3h cmp a = 3683 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3684 let m = (l + r) / 2 in 3685 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3686 let pivot = if cmp al am <= 0 then 3687 if cmp am ar <= 0 then am 3688 else if cmp al ar <= 0 then ar 3689 else al 3690 else 3691 if cmp al ar <= 0 then al 3692 else if cmp am ar <= 0 then ar 3693 else am 3694 in 3695 let p1 = ref l and p2 = ref l and p3 = ref r in 3696 while !p2 < !p3 do 3697 let e = a.(!p2) in 3698 let c = cmp e pivot in 3699 if c > 0 then begin 3700 decr p3; 3701 a.(!p2) <- a.(!p3); 3702 a.(!p3) <- e; 3703 end else if c < 0 then begin 3704 incr p2; 3705 end else begin 3706 a.(!p2) <- a.(!p1); 3707 a.(!p1) <- e; 3708 incr p1; 3709 incr p2; 3710 end 3711 done; 3712 while !p1 > l do 3713 decr p1; 3714 decr p2; 3715 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3716 done; 3717 let len1 = !p2 - l and len2 = r - !p3 in 3718 if len1 > cutoff then 3719 if len2 > cutoff then begin 3720 if len1 < len2 3721 then (qsort l !p2; qsort !p3 r) 3722 else (qsort !p3 r; qsort l !p2) 3723 end else qsort l !p2 3724 else if len2 > cutoff then qsort !p3 r; 3725 in 3726 let l = Array.length a in 3727 if l > 1 then begin 3728 qsort 0 l; 3729 let mini = ref 0 in 3730 for i = 0 to (min l cutoff) - 1 do 3731 if cmp a.(i) a.(!mini) < 0 then mini := i; 3732 done; 3733 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3734 for i = 1 to l - 1 do 3735 let e = a.(i) in 3736 let j = ref (i - 1) in 3737 while cmp a.(!j) e > 0 do 3738 a.(!j + 1) <- a.(!j); 3739 decr j; 3740 done; 3741 a.(!j + 1) <- e; 3742 done; 3743 end; 3744;; 3745 3746let cutoff = 9;; 3747let aquick_3i cmp a = 3748 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3749 let m = (l + r) / 2 in 3750 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3751 let pivot = if cmp al am <= 0 then 3752 if cmp am ar <= 0 then am 3753 else if cmp al ar <= 0 then ar 3754 else al 3755 else 3756 if cmp al ar <= 0 then al 3757 else if cmp am ar <= 0 then ar 3758 else am 3759 in 3760 let p1 = ref l and p2 = ref l and p3 = ref r in 3761 while !p2 < !p3 do 3762 let e = a.(!p2) in 3763 let c = cmp e pivot in 3764 if c > 0 then begin 3765 decr p3; 3766 a.(!p2) <- a.(!p3); 3767 a.(!p3) <- e; 3768 end else if c < 0 then begin 3769 incr p2; 3770 end else begin 3771 a.(!p2) <- a.(!p1); 3772 a.(!p1) <- e; 3773 incr p1; 3774 incr p2; 3775 end 3776 done; 3777 while !p1 > l do 3778 decr p1; 3779 decr p2; 3780 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3781 done; 3782 let len1 = !p2 - l and len2 = r - !p3 in 3783 if len1 > cutoff then 3784 if len2 > cutoff then begin 3785 if len1 < len2 3786 then (qsort l !p2; qsort !p3 r) 3787 else (qsort !p3 r; qsort l !p2) 3788 end else qsort l !p2 3789 else if len2 > cutoff then qsort !p3 r; 3790 in 3791 let l = Array.length a in 3792 if l > 1 then begin 3793 qsort 0 l; 3794 let mini = ref 0 in 3795 for i = 0 to (min l cutoff) - 1 do 3796 if cmp a.(i) a.(!mini) < 0 then mini := i; 3797 done; 3798 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3799 for i = 1 to l - 1 do 3800 let e = a.(i) in 3801 let j = ref (i - 1) in 3802 while cmp a.(!j) e > 0 do 3803 a.(!j + 1) <- a.(!j); 3804 decr j; 3805 done; 3806 a.(!j + 1) <- e; 3807 done; 3808 end; 3809;; 3810 3811let cutoff = 10;; 3812let aquick_3j cmp a = 3813 let rec qsort l r = (* ASSUMES r - l >= 2 *) 3814 let m = (l + r) / 2 in 3815 let al = a.(l) and am = a.(m) and ar = a.(r - 1) in 3816 let pivot = if cmp al am <= 0 then 3817 if cmp am ar <= 0 then am 3818 else if cmp al ar <= 0 then ar 3819 else al 3820 else 3821 if cmp al ar <= 0 then al 3822 else if cmp am ar <= 0 then ar 3823 else am 3824 in 3825 let p1 = ref l and p2 = ref l and p3 = ref r in 3826 while !p2 < !p3 do 3827 let e = a.(!p2) in 3828 let c = cmp e pivot in 3829 if c > 0 then begin 3830 decr p3; 3831 a.(!p2) <- a.(!p3); 3832 a.(!p3) <- e; 3833 end else if c < 0 then begin 3834 incr p2; 3835 end else begin 3836 a.(!p2) <- a.(!p1); 3837 a.(!p1) <- e; 3838 incr p1; 3839 incr p2; 3840 end 3841 done; 3842 while !p1 > l do 3843 decr p1; 3844 decr p2; 3845 let e = a.(!p1) in a.(!p1) <- a.(!p2); a.(!p2) <- e; 3846 done; 3847 let len1 = !p2 - l and len2 = r - !p3 in 3848 if len1 > cutoff then 3849 if len2 > cutoff then begin 3850 if len1 < len2 3851 then (qsort l !p2; qsort !p3 r) 3852 else (qsort !p3 r; qsort l !p2) 3853 end else qsort l !p2 3854 else if len2 > cutoff then qsort !p3 r; 3855 in 3856 let l = Array.length a in 3857 if l > 1 then begin 3858 qsort 0 l; 3859 let mini = ref 0 in 3860 for i = 0 to (min l cutoff) - 1 do 3861 if cmp a.(i) a.(!mini) < 0 then mini := i; 3862 done; 3863 let e = a.(0) in a.(0) <- a.(!mini); a.(!mini) <- e; 3864 for i = 1 to l - 1 do 3865 let e = a.(i) in 3866 let j = ref (i - 1) in 3867 while cmp a.(!j) e > 0 do 3868 a.(!j + 1) <- a.(!j); 3869 decr j; 3870 done; 3871 a.(!j + 1) <- e; 3872 done; 3873 end; 3874;; 3875 3876(************************************************************************) 3877(* Heap sort on arrays (top-down, ternary) *) 3878 3879let aheap_1 cmp a = 3880 let l = ref (Array.length a) in 3881 let l3 = ref ((!l + 1) / 3) in (* l3 is the first element without sons *) 3882 let maxson i = (* ASSUMES i < !l3 *) 3883 let i31 = i+i+i+1 in 3884 let x = ref i31 in 3885 if i31+2 < !l then begin 3886 if cmp a.(i31) a.(i31+1) < 0 then x := i31+1; 3887 if cmp a.(!x) a.(i31+2) < 0 then x := i31+2; 3888 !x 3889 end else begin 3890 if i31+1 < !l && cmp a.(i31) a.(i31+1) < 0 3891 then i31+1 3892 else i31 3893 end 3894 in 3895 let rec trickledown i e = (* ASSUMES i < !l3 *) 3896 let j = maxson i in 3897 if cmp a.(j) e > 0 then begin 3898 a.(i) <- a.(j); 3899 if j < !l3 then trickledown j e else a.(j) <- e; 3900 end else begin 3901 a.(i) <- e; 3902 end; 3903 in 3904 for i = !l3 - 1 downto 0 do trickledown i a.(i); done; 3905 let m = ref (!l + 1 - 3 * !l3) in 3906 while !l > 2 do 3907 decr l; 3908 if !m = 0 then (m := 2; decr l3) else decr m; 3909 let e = a.(!l) in 3910 a.(!l) <- a.(0); 3911 trickledown 0 e; 3912 done; 3913 if !l > 1 then begin let e = a.(1) in a.(1) <- a.(0); a.(0) <- e; end; 3914;; 3915 3916(************************************************************************) 3917(* Heap sort on arrays (top-down, binary) *) 3918 3919(* FIXME try partial application of trickledown (merge with down) *) 3920(* FIXME try to expand maxson in trickledown; delete the exception. *) 3921 3922let aheap_2 cmp a = 3923 let maxson l i e = 3924 let i21 = i + i + 1 in 3925 if i21 + 1 < l && cmp a.(i21) a.(i21+1) < 0 3926 then i21 + 1 3927 else if i21 < l then i21 else (a.(i) <- e; raise Exit) 3928 in 3929 let rec trickledown l i e = 3930 let j = maxson l i e in 3931 if cmp a.(j) e > 0 then begin 3932 a.(i) <- a.(j); 3933 trickledown l j e; 3934 end else begin 3935 a.(i) <- e; 3936 end; 3937 in 3938 let down l i e = try trickledown l i e with Exit -> () in 3939 let l = Array.length a in 3940 for i = l / 2 -1 downto 0 do down l i a.(i); done; 3941 for i = l - 1 downto 1 do 3942 let e = a.(i) in 3943 a.(i) <- a.(0); 3944 down i 0 e; 3945 done; 3946;; 3947 3948(************************************************************************) 3949(* Heap sort on arrays (bottom-up, ternary) *) 3950 3951exception Bottom of int;; 3952 3953let aheap_3 cmp a = 3954 let maxson l i = 3955 let i31 = i+i+i+1 in 3956 let x = ref i31 in 3957 if i31+2 < l then begin 3958 if cmp a.(i31) a.(i31+1) < 0 then x := i31+1; 3959 if cmp a.(!x) a.(i31+2) < 0 then x := i31+2; 3960 !x 3961 end else 3962 if i31+1 < l && cmp a.(i31) a.(i31+1) < 0 3963 then i31+1 3964 else if i31 < l then i31 else raise (Bottom i) 3965 in 3966 let rec trickledown l i e = 3967 let j = maxson l i in 3968 if cmp a.(j) e > 0 then begin 3969 a.(i) <- a.(j); 3970 trickledown l j e; 3971 end else begin 3972 a.(i) <- e; 3973 end; 3974 in 3975 let rec trickle l i e = try trickledown l i e with Bottom i -> a.(i) <- e in 3976 let rec bubbledown l i = 3977 let j = maxson l i in 3978 a.(i) <- a.(j); 3979 bubbledown l j; 3980 in 3981 let bubble l i = try bubbledown l i with Bottom i -> i in 3982 let rec trickleup i e = 3983 let father = (i - 1) / 3 in 3984 assert (i <> father); 3985 if cmp a.(father) e < 0 then begin 3986 a.(i) <- a.(father); 3987 if father > 0 then trickleup father e else a.(0) <- e; 3988 end else begin 3989 a.(i) <- e; 3990 end; 3991 in 3992 let l = Array.length a in 3993 for i = (l + 1) / 3 - 1 downto 0 do trickle l i a.(i); done; 3994 for i = l - 1 downto 2 do 3995 let e = a.(i) in 3996 a.(i) <- a.(0); 3997 trickleup (bubble i 0) e; 3998 done; 3999 if l > 1 then (let e = a.(1) in a.(1) <- a.(0); a.(0) <- e); 4000;; 4001 4002(************************************************************************) 4003(* Heap sort on arrays (bottom-up, binary) *) 4004 4005let aheap_4 cmp a = 4006 let maxson l i = 4007 let i21 = i + i + 1 in 4008 if i21 + 1 < l && cmp a.(i21) a.(i21 + 1) < 0 4009 then i21 + 1 4010 else if i21 < l then i21 else raise (Bottom i) 4011 in 4012 let rec trickledown l i e = 4013 let j = maxson l i in 4014 if cmp a.(j) e > 0 then begin 4015 a.(i) <- a.(j); 4016 trickledown l j e; 4017 end else begin 4018 a.(i) <- e; 4019 end; 4020 in 4021 let trickle l i e = try trickledown l i e with Bottom i -> a.(i) <- e in 4022 let rec bubbledown l i = 4023 let j = maxson l i in 4024 a.(i) <- a.(j); 4025 bubbledown l j; 4026 in 4027 let bubble l i = try bubbledown l i with Bottom i -> i in 4028 let rec trickleup i e = 4029 let father = (i - 1) / 2 in 4030 assert (i <> father); 4031 if cmp a.(father) e < 0 then begin 4032 a.(i) <- a.(father); 4033 if father > 0 then trickleup father e else a.(0) <- e; 4034 end else begin 4035 a.(i) <- e; 4036 end; 4037 in 4038 let l = Array.length a in 4039 for i = l / 2 - 1 downto 0 do trickle l i a.(i); done; 4040 for i = l - 1 downto 2 do 4041 let e = a.(i) in 4042 a.(i) <- a.(0); 4043 trickleup (bubble i 0) e; 4044 done; 4045 if l > 1 then (let e = a.(1) in a.(1) <- a.(0); a.(0) <- e); 4046;; 4047 4048(************************************************************************) 4049(* heap sort, top-down, ternary, recursive final loop *) 4050 4051let aheap_5 cmp a = 4052 let maxson l i = (* ASSUMES i < (l+1)/3 *) 4053 let i31 = i+i+i+1 in 4054 let x = ref i31 in 4055 if i31+2 < l then begin 4056 if cmp a.(i31) a.(i31+1) < 0 then x := i31+1; 4057 if cmp a.(!x) a.(i31+2) < 0 then x := i31+2; 4058 !x 4059 end else begin 4060 if i31+1 < l && cmp a.(i31) a.(i31+1) < 0 4061 then i31+1 4062 else i31 4063 end 4064 in 4065 let rec trickledown l l3 i e = (* ASSUMES i < l3 *) 4066 let j = maxson l i in 4067 if cmp a.(j) e > 0 then begin 4068 a.(i) <- a.(j); 4069 if j < l3 then trickledown l l3 j e else a.(j) <- e; 4070 end else begin 4071 a.(i) <- e; 4072 end; 4073 in 4074 let l = Array.length a in 4075 let l3 = (l + 1) / 3 in 4076 for i = l3 - 1 downto 0 do trickledown l l3 i a.(i); done; 4077 let rec loop0 l l3 = 4078 let e = a.(l) in 4079 a.(l) <- a.(0); 4080 trickledown l l3 0 e; 4081 loop2 (l-1) (l3-1); 4082 and loop1 l l3 = 4083 let e = a.(l) in 4084 a.(l) <- a.(0); 4085 trickledown l l3 0 e; 4086 loop0 (l-1) l3; 4087 and loop2 l l3 = 4088 if l > 1 then begin 4089 let e = a.(l) in 4090 a.(l) <- a.(0); 4091 trickledown l l3 0 e; 4092 loop1 (l-1) l3; 4093 end else begin 4094 let e = a.(1) in a.(1) <- a.(0); a.(0) <- e; 4095 end; 4096 in 4097 if l > 1 then 4098 match l + 1 - 3 * l3 with 4099 | 0 -> loop2 (l-1) (l3-1); 4100 | 1 -> loop0 (l-1) l3; 4101 | 2 -> loop1 (l-1) l3; 4102 | _ -> assert false; 4103;; 4104 4105(************************************************************************) 4106(* heap sort, top-down, ternary, with exception *) 4107 4108let aheap_6 cmp a = 4109 let maxson e l i = 4110 let i31 = i + i + i + 1 in 4111 let x = ref i31 in 4112 if i31+2 < l then begin 4113 if cmp a.(i31) a.(i31+1) < 0 then x := i31+1; 4114 if cmp a.(!x) a.(i31+2) < 0 then x := i31+2; 4115 !x 4116 end else begin 4117 if i31+1 < l && cmp a.(i31) a.(i31+1) < 0 4118 then i31+1 4119 else if i31 < l then i31 else (a.(i) <- e; raise Exit) 4120 end 4121 in 4122 let rec trickledown e l i = 4123 let j = maxson e l i in 4124 if cmp a.(j) e > 0 then begin 4125 a.(i) <- a.(j); 4126 trickledown e l j; 4127 end else begin 4128 a.(i) <- e; 4129 end; 4130 in 4131 let down e l i = try trickledown e l i with Exit -> (); in 4132 let l = Array.length a in 4133 for i = (l + 1) / 3 - 1 downto 0 do down a.(i) l i; done; 4134 for i = l - 1 downto 2 do 4135 let e = a.(i) in 4136 a.(i) <- a.(0); 4137 down e i 0; 4138 done; 4139 if l > 1 then (let e = a.(1) in a.(1) <- a.(0); a.(0) <- e); 4140;; 4141 4142(* FIXME try cutoff for heapsort *) 4143 4144(************************************************************************) 4145(* Insertion sort with dichotomic search *) 4146 4147let ainsertion_1 cmp a = 4148 let rec dicho l r e = 4149 if l = r then l else begin 4150 let m = (l + r) / 2 in 4151 if cmp a.(m) e <= 0 4152 then dicho (m+1) r e 4153 else dicho l m e 4154 end 4155 in 4156 for i = 1 to Array.length a - 1 do 4157 let e = a.(i) in 4158 let j = dicho 0 i e in 4159 Array.blit a j a (j + 1) (i - j); 4160 a.(j) <- e; 4161 done; 4162;; 4163 4164(************************************************************************) 4165(* merge sort on lists via arrays *) 4166 4167let array_to_list_in_place a = 4168 let l = Array.length a in 4169 let rec loop accu n p = 4170 if p <= 0 then accu else begin 4171 if p = n then begin 4172 Obj.truncate (Obj.repr a) p; 4173 loop (a.(p-1) :: accu) (n-1000) (p-1) 4174 end else begin 4175 loop (a.(p-1) :: accu) n (p-1) 4176 end 4177 end 4178 in 4179 loop [] l l 4180;; 4181 4182let array_of_list l len = 4183 match l with 4184 | [] -> [| |] 4185 | h::t -> 4186 let a = Array.make len h in 4187 let rec loop i l = 4188 match l with 4189 | [] -> () 4190 | h::t -> a.(i) <- h; loop (i+1) t 4191 in 4192 loop 1 t; 4193 a 4194;; 4195 4196let lmerge_0a cmp l = 4197 let a = Array.of_list l in 4198 amerge_1e cmp a; 4199 array_to_list_in_place a 4200;; 4201 4202let lmerge_0b cmp l = 4203 let len = List.length l in 4204 if len > 256 then Gc.minor (); 4205 let a = array_of_list l len in 4206 amerge_1e cmp a; 4207 array_to_list_in_place a 4208;; 4209 4210let lshell_0 cmp l = 4211 let a = Array.of_list l in 4212 ashell_2 cmp a; 4213 array_to_list_in_place a 4214;; 4215 4216let lquick_0 cmp l = 4217 let a = Array.of_list l in 4218 aquick_3f cmp a; 4219 array_to_list_in_place a 4220;; 4221 4222(************************************************************************) 4223(* merge sort on arrays via lists *) 4224 4225let amerge_0 cmp a = (* cutoff is not yet used *) 4226 let l = lmerge_4e cmp (Array.to_list a) in 4227 let rec loop i = function 4228 | [] -> () 4229 | h::t -> a.(i) <- h; loop (i + 1) t 4230 in 4231 loop 0 l 4232;; 4233 4234(************************************************************************) 4235 4236let lold = [ 4237 "Sort.list", Sort.list, true; 4238 "lmerge_3", lmerge_3, false; 4239 "lmerge_4a", lmerge_4a, true; 4240];; 4241 4242let lnew = [ 4243 "List.stable_sort", List.stable_sort, true; 4244 4245 "lmerge_0a", lmerge_0a, true; 4246 "lmerge_0b", lmerge_0b, true; 4247 "lshell_0", lshell_0, false; 4248 "lquick_0", lquick_0, false; 4249 4250 "lmerge_1a", lmerge_1a, true; 4251 "lmerge_1b", lmerge_1b, true; 4252 "lmerge_1c", lmerge_1c, true; 4253 "lmerge_1d", lmerge_1d, true; 4254 4255 "lmerge_4b", lmerge_4b, true; 4256 "lmerge_4c", lmerge_4c, true; 4257 "lmerge_4d", lmerge_4d, true; 4258 "lmerge_4e", lmerge_4e, true; 4259 4260 "lmerge_5a", lmerge_5a, true; 4261 "lmerge_5b", lmerge_5b, true; 4262 "lmerge_5c", lmerge_5c, true; 4263 "lmerge_5d", lmerge_5d, true; 4264];; 4265let anew = [ 4266 "Array.stable_sort", Array.stable_sort, true; 4267 "Array.sort", Array.sort, false; 4268 4269 "amerge_0", amerge_0, true; 4270 4271 "amerge_1a", amerge_1a, true; 4272 "amerge_1b", amerge_1b, true; 4273 "amerge_1c", amerge_1c, true; 4274 "amerge_1d", amerge_1d, true; 4275 "amerge_1e", amerge_1e, true; 4276 "amerge_1f", amerge_1f, true; 4277 "amerge_1g", amerge_1g, true; 4278 "amerge_1h", amerge_1h, true; 4279 "amerge_1i", amerge_1i, true; 4280 "amerge_1j", amerge_1j, true; 4281 4282 "amerge_3a", amerge_3a, true; 4283 "amerge_3b", amerge_3b, true; 4284 "amerge_3c", amerge_3c, true; 4285 "amerge_3d", amerge_3d, true; 4286 "amerge_3e", amerge_3e, true; 4287 "amerge_3f", amerge_3f, true; 4288 "amerge_3g", amerge_3g, true; 4289 "amerge_3h", amerge_3h, true; 4290 "amerge_3i", amerge_3i, true; 4291 "amerge_3j", amerge_3j, true; 4292 4293 "ashell_1", ashell_1, false; 4294 "ashell_2", ashell_2, false; 4295 "ashell_3", ashell_3, false; 4296 "ashell_4", ashell_4, false; 4297 4298 "aquick_1a", aquick_1a, false; 4299 "aquick_1b", aquick_1b, false; 4300 "aquick_1c", aquick_1c, false; 4301 "aquick_1d", aquick_1d, false; 4302 "aquick_1e", aquick_1e, false; 4303 "aquick_1f", aquick_1f, false; 4304 "aquick_1g", aquick_1g, false; 4305 4306 "aquick_2a", aquick_2a, false; 4307 "aquick_2b", aquick_2b, false; 4308 "aquick_2c", aquick_2c, false; 4309 "aquick_2d", aquick_2d, false; 4310 "aquick_2e", aquick_2e, false; 4311 "aquick_2f", aquick_2f, false; 4312 "aquick_2g", aquick_2g, false; 4313 4314 "aquick_3a", aquick_3a, false; 4315 "aquick_3b", aquick_3b, false; 4316 "aquick_3c", aquick_3c, false; 4317 "aquick_3d", aquick_3d, false; 4318 "aquick_3e", aquick_3e, false; 4319 "aquick_3f", aquick_3f, false; 4320 "aquick_3g", aquick_3g, false; 4321 "aquick_3h", aquick_3h, false; 4322 "aquick_3i", aquick_3i, false; 4323 "aquick_3j", aquick_3j, false; 4324 4325 "aheap_1", aheap_1, false; 4326 "aheap_2", aheap_2, false; 4327 "aheap_3", aheap_3, false; 4328 "aheap_4", aheap_4, false; 4329 "aheap_5", aheap_5, false; 4330 "aheap_6", aheap_6, false; 4331 4332 "ainsertion_1", ainsertion_1, true; 4333];; 4334 4335(************************************************************************) 4336(* main program *) 4337 4338type mode = Test_std | Test | Bench1 | Bench2 | Bench3;; 4339 4340let size = ref 22 4341and mem = ref 0 4342and mode = ref Test_std 4343and only = ref [] 4344;; 4345 4346let usage = "Usage: sorts [-size <table size>] [-mem <memory size>]\n\ 4347 \032 [-seed <random seed>] [-test|-bench]" 4348;; 4349 4350let options = [ 4351 "-size", Arg.Int ((:=) size), " Maximum size for benchmarks (default 22)"; 4352 "-meg",Arg.Int ((:=) mem)," How many megabytes to preallocate (default 0)"; 4353 "-seed", Arg.Int ((:=) seed), " PRNG seed (default 0)"; 4354 "-teststd", Arg.Unit (fun () -> mode := Test_std), " Test stdlib (default)"; 4355 "-test", Arg.Unit (fun () -> mode := Test), " Select test mode"; 4356 "-bench1", Arg.Unit (fun () -> mode := Bench1), " Select bench mode 1"; 4357 "-bench2", Arg.Unit (fun () -> mode := Bench2), " Select bench mode 2"; 4358 "-bench3", Arg.Unit (fun () -> mode := Bench3), " Select bench mode 3"; 4359 "-fn", Arg.String (fun x -> only := x :: !only), 4360 " <function> Test/Bench this function (default all)"; 4361];; 4362let anonymous x = raise (Arg.Bad ("unrecognised option "^x));; 4363 4364let main () = 4365 Arg.parse options anonymous usage; 4366 4367 Printf.printf "Command line arguments are:"; 4368 for i = 1 to Array.length Sys.argv - 1 do 4369 Printf.printf " %s" Sys.argv.(i); 4370 done; 4371 Printf.printf "\n"; 4372 4373 ignore (String.create (1048576 * !mem)); 4374 Gc.full_major (); 4375(* 4376 let a2l = Array.to_list in 4377 let l2ak x y = Array.of_list x in 4378 let id = fun x -> x in 4379 let fst x y = x in 4380 let snd x y = y in 4381*) 4382 let benchonly f x y z t = 4383 match !only with 4384 | [] -> f x y z t 4385 | l -> if List.mem y l then f x y z t 4386 in 4387 let testonly x1 x2 x3 x4 x5 x6 = 4388 match !only with 4389 | [] -> test x1 x2 x3 x4 x5 x6 4390 | l -> if List.mem x1 l then test x1 x2 x3 x4 x5 x6 4391 in 4392 4393 match !mode with 4394 | Test_std -> begin 4395 testonly "List.sort" false List.sort List.sort lc lc; 4396 testonly "List.stable_sort" true List.stable_sort List.stable_sort lc lc; 4397 testonly "Array.sort" false Array.sort Array.sort ac ac; 4398 testonly "Array.stable_sort" true Array.stable_sort Array.stable_sort 4399 ac ac; 4400 printf "Number of tests failed: %d\n" !numfailed; 4401 end; 4402 | Test -> begin 4403 for i = 0 to List.length lold - 1 do 4404 let (name, f1, stable) = List.nth lold i in 4405 let (_, f2, _) = List.nth lold i in 4406 testonly name stable f1 f2 ll ll; 4407 done; 4408 testonly "Sort.array" false Sort.array Sort.array al al; 4409 for i = 0 to List.length lnew - 1 do 4410 let (name, f1, stable) = List.nth lnew i in 4411 let (_, f2, _) = List.nth lnew i in 4412 testonly name stable f1 f2 lc lc; 4413 done; 4414 for i = 0 to List.length anew - 1 do 4415 let (name, f1, stable) = List.nth anew i in 4416 let (_, f2, _) = List.nth anew i in 4417 testonly name stable f1 f2 ac ac; 4418 done; 4419 printf "Number of tests failed: %d\n" !numfailed; 4420 end; 4421 | Bench1 -> begin 4422 let ba = fun x y z -> benchonly bench1a !size x y z 4423 and bb = fun x y z -> benchonly bench1b !size x y z 4424 and bc = fun x y z -> benchonly bench1c !size x y z 4425 in 4426 for i = 0 to List.length lold - 1 do 4427 let (name, f, stable) = List.nth lold i in ba name f ll; 4428 let (name, f, stable) = List.nth lold i in bb name f ll; 4429 let (name, f, stable) = List.nth lold i in bc name f ll; 4430 done; 4431 ba "Sort.array" Sort.array al; 4432 bb "Sort.array" Sort.array al; 4433 bc "Sort.array" Sort.array al; 4434 for i = 0 to List.length lnew - 1 do 4435 let (name, f, stable) = List.nth lnew i in ba name f lc; 4436 let (name, f, stable) = List.nth lnew i in bb name f lc; 4437 let (name, f, stable) = List.nth lnew i in bc name f lc; 4438 done; 4439 for i = 0 to List.length anew - 1 do 4440 let (name, f, stable) = List.nth anew i in ba name f ac; 4441 let (name, f, stable) = List.nth anew i in bb name f ac; 4442 let (name, f, stable) = List.nth anew i in bc name f ac; 4443 done; 4444 end; 4445 | Bench2 -> begin 4446 let b = fun x y z -> benchonly bench2 !size x y z in 4447 for i = 0 to List.length lold - 1 do 4448 let (name, f, stable) = List.nth lold i in b name f ll; 4449 done; 4450 b "Sort.array" Sort.array al; 4451 for i = 0 to List.length lnew - 1 do 4452 let (name, f, stable) = List.nth lnew i in b name f lc; 4453 done; 4454 for i = 0 to List.length anew - 1 do 4455 let (name, f, stable) = List.nth anew i in b name f ac; 4456 done; 4457 end; 4458 | Bench3 -> begin 4459 let ba = fun x y z -> benchonly bench3a !size x y z 4460 and bb = fun x y z -> benchonly bench3b !size x y z 4461 and bc = fun x y z -> benchonly bench3c !size x y z 4462 in 4463 for i = 0 to List.length lold - 1 do 4464 let (name, f, stable) = List.nth lold i in ba name f ll; 4465 let (name, f, stable) = List.nth lold i in bb name f ll; 4466 let (name, f, stable) = List.nth lold i in bc name f ll; 4467 done; 4468 for i = 0 to List.length lnew - 1 do 4469 let (name, f, stable) = List.nth lnew i in ba name f lc; 4470 let (name, f, stable) = List.nth lnew i in bb name f lc; 4471 let (name, f, stable) = List.nth lnew i in bc name f lc; 4472 done; 4473 end; 4474;; 4475 4476if not !Sys.interactive then Printexc.catch main ();; 4477