src/libstd/sort.rs

   1 // Copyright 2012 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Sorting methods
  12
  13 use core::cmp::{Eq, Ord};
  14 use core::util;
  15 use core::vec::len;
  16 use core::vec;
  17
  18 type Le<'self, T> = &'self fn(v1: &T, v2: &T) -> bool;
  19
  20 /**
  21  * Merge sort. Returns a new vector containing the sorted list.
  22  *
  23  * Has worst case O(n log n) performance, best case O(n), but
  24  * is not space efficient. This is a stable sort.
  25  */
  26 pub fn merge_sort<T:Copy>(v: &const [T], le: Le<T>) -> ~[T] {
  27     type Slice = (uint, uint);
  28
  29     return merge_sort_(v, (0u, len(v)), le);
  30
  31     fn merge_sort_<T:Copy>(v: &const [T], slice: Slice, le: Le<T>)
  32         -> ~[T] {
  33         let begin = slice.first();
  34         let end = slice.second();
  35
  36         let v_len = end - begin;
  37         if v_len == 0 { return ~[]; }
  38         if v_len == 1 { return ~[v[begin]]; }
  39
  40         let mid = v_len / 2 + begin;
  41         let a = (begin, mid);
  42         let b = (mid, end);
  43         return merge(le, merge_sort_(v, a, le), merge_sort_(v, b, le));
  44     }
  45
  46     fn merge<T:Copy>(le: Le<T>, a: &[T], b: &[T]) -> ~[T] {
  47         let mut rs = vec::with_capacity(len(a) + len(b));
  48         let a_len = len(a);
  49         let mut a_ix = 0;
  50         let b_len = len(b);
  51         let mut b_ix = 0;
  52         while a_ix < a_len && b_ix < b_len {
  53             if le(&a[a_ix], &b[b_ix]) {
  54                 rs.push(a[a_ix]);
  55                 a_ix += 1;
  56             } else { rs.push(b[b_ix]); b_ix += 1; }
  57         }
  58         rs.push_all(vec::slice(a, a_ix, a_len));
  59         rs.push_all(vec::slice(b, b_ix, b_len));
  60         rs
  61     }
  62 }
  63
  64 fn part<T>(arr: &mut [T], left: uint,
  65            right: uint, pivot: uint, compare_func: Le<T>) -> uint {
  66     arr[pivot] <-> arr[right];
  67     let mut storage_index: uint = left;
  68     let mut i: uint = left;
  69     while i < right {
  70         let a: &mut T = &mut arr[i];
  71         let b: &mut T = &mut arr[right];
  72         if compare_func(a, b) {
  73             arr[i] <-> arr[storage_index];
  74             storage_index += 1;
  75         }
  76         i += 1;
  77     }
  78     arr[storage_index] <-> arr[right];
  79     return storage_index;
  80 }
  81
  82 fn qsort<T>(arr: &mut [T], left: uint,
  83             right: uint, compare_func: Le<T>) {
  84     if right > left {
  85         let pivot = (left + right) / 2u;
  86         let new_pivot = part::<T>(arr, left, right, pivot, compare_func);
  87         if new_pivot != 0u {
  88             // Need to do this check before recursing due to overflow
  89             qsort::<T>(arr, left, new_pivot - 1u, compare_func);
  90         }
  91         qsort::<T>(arr, new_pivot + 1u, right, compare_func);
  92     }
  93 }
  94
  95 /**
  96  * Quicksort. Sorts a mut vector in place.
  97  *
  98  * Has worst case O(n^2) performance, average case O(n log n).
  99  * This is an unstable sort.
 100  */
 101 pub fn quick_sort<T>(arr: &mut [T], compare_func: Le<T>) {
 102     if len::<T>(arr) == 0u { return; }
 103     qsort::<T>(arr, 0u, len::<T>(arr) - 1u, compare_func);
 104 }
 105
 106 fn qsort3<T:Copy + Ord + Eq>(arr: &mut [T], left: int, right: int) {
 107     if right <= left { return; }
 108     let v: T = arr[right];
 109     let mut i: int = left - 1;
 110     let mut j: int = right;
 111     let mut p: int = i;
 112     let mut q: int = j;
 113     loop {
 114         i += 1;
 115         while arr[i] < v { i += 1; }
 116         j -= 1;
 117         while v < arr[j] {
 118             if j == left { break; }
 119             j -= 1;
 120         }
 121         if i >= j { break; }
 122         arr[i] <-> arr[j];
 123         if arr[i] == v {
 124             p += 1;
 125             arr[p] <-> arr[i];
 126         }
 127         if v == arr[j] {
 128             q -= 1;
 129             arr[j] <-> arr[q];
 130         }
 131     }
 132     arr[i] <-> arr[right];
 133     j = i - 1;
 134     i += 1;
 135     let mut k: int = left;
 136     while k < p {
 137         arr[k] <-> arr[j];
 138         k += 1;
 139         j -= 1;
 140         if k == len::<T>(arr) as int { break; }
 141     }
 142     k = right - 1;
 143     while k > q {
 144         arr[i] <-> arr[k];
 145         k -= 1;
 146         i += 1;
 147         if k == 0 { break; }
 148     }
 149     qsort3::<T>(arr, left, j);
 150     qsort3::<T>(arr, i, right);
 151 }
 152
 153 /**
 154  * Fancy quicksort. Sorts a mut vector in place.
 155  *
 156  * Based on algorithm presented by ~[Sedgewick and Bentley]
 157  * (http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf).
 158  * According to these slides this is the algorithm of choice for
 159  * 'randomly ordered keys, abstract compare' & 'small number of key values'.
 160  *
 161  * This is an unstable sort.
 162  */
 163 pub fn quick_sort3<T:Copy + Ord + Eq>(arr: &mut [T]) {
 164     if arr.len() <= 1 { return; }
 165     qsort3(arr, 0, (arr.len() - 1) as int);
 166 }
 167
 168 pub trait Sort {
 169     fn qsort(self);
 170 }
 171
 172 impl<'self, T:Copy + Ord + Eq> Sort for &'self mut [T] {
 173     fn qsort(self) { quick_sort3(self); }
 174 }
 175
 176 static MIN_MERGE: uint = 64;
 177 static MIN_GALLOP: uint = 7;
 178 static INITIAL_TMP_STORAGE: uint = 128;
 179
 180 pub fn tim_sort<T:Copy + Ord>(array: &mut [T]) {
 181     let size = array.len();
 182     if size < 2 {
 183         return;
 184     }
 185
 186     if size < MIN_MERGE {
 187         let init_run_len = count_run_ascending(array);
 188         binarysort(array, init_run_len);
 189         return;
 190     }
 191
 192     let mut ms = MergeState();
 193     let min_run = min_run_length(size);
 194
 195     let mut idx = 0;
 196     let mut remaining = size;
 197     loop {
 198         let arr = vec::mut_slice(array, idx, size);
 199         let mut run_len: uint = count_run_ascending(arr);
 200
 201         if run_len < min_run {
 202             let force = if remaining <= min_run {remaining} else {min_run};
 203             let slice = vec::mut_slice(arr, 0, force);
 204             binarysort(slice, run_len);
 205             run_len = force;
 206         }
 207
 208         ms.push_run(idx, run_len);
 209         ms.merge_collapse(array);
 210
 211         idx += run_len;
 212         remaining -= run_len;
 213         if remaining == 0 { break; }
 214     }
 215
 216     ms.merge_force_collapse(array);
 217 }
 218
 219 fn binarysort<T:Copy + Ord>(array: &mut [T], start: uint) {
 220     let size = array.len();
 221     let mut start = start;
 222     assert!(start <= size);
 223
 224     if start == 0 { start += 1; }
 225
 226     while start < size {
 227         let pivot = array[start];
 228         let mut left = 0;
 229         let mut right = start;
 230         assert!(left <= right);
 231
 232         while left < right {
 233             let mid = (left + right) >> 1;
 234             if pivot < array[mid] {
 235                 right = mid;
 236             } else {
 237                 left = mid+1;
 238             }
 239         }
 240         assert!(left == right);
 241         let n = start-left;
 242
 243         copy_vec(array, left+1, array, left, n);
 244         array[left] = pivot;
 245         start += 1;
 246     }
 247 }
 248
 249 // Reverse the order of elements in a slice, in place
 250 fn reverse_slice<T>(v: &mut [T], start: uint, end:uint) {
 251     let mut i = start;
 252     while i < end / 2 {
 253         util::swap(&mut v[i], &mut v[end - i - 1]);
 254         i += 1;
 255     }
 256 }
 257
 258 fn min_run_length(n: uint) -> uint {
 259     let mut n = n;
 260     let mut r = 0;   // becomes 1 if any 1 bits are shifted off
 261
 262     while n >= MIN_MERGE {
 263         r |= n & 1;
 264         n >>= 1;
 265     }
 266     return n + r;
 267 }
 268
 269 fn count_run_ascending<T:Copy + Ord>(array: &mut [T]) -> uint {
 270     let size = array.len();
 271     assert!(size > 0);
 272     if size == 1 { return 1; }
 273
 274     let mut run = 2;
 275     if array[1] < array[0] {
 276         while run < size && array[run] < array[run-1] {
 277             run += 1;
 278         }
 279         reverse_slice(array, 0, run);
 280     } else {
 281         while run < size && array[run] >= array[run-1] {
 282             run += 1;
 283         }
 284     }
 285
 286     return run;
 287 }
 288
 289 fn gallop_left<T:Copy + Ord>(key: &const T,
 290                              array: &const [T],
 291                              hint: uint)
 292                           -> uint {
 293     let size = array.len();
 294     assert!(size != 0 && hint < size);
 295
 296     let mut last_ofs = 0;
 297     let mut ofs = 1;
 298
 299     if *key > array[hint] {
 300         // Gallop right until array[hint+last_ofs] < key <= array[hint+ofs]
 301         let max_ofs = size - hint;
 302         while ofs < max_ofs && *key > array[hint+ofs] {
 303             last_ofs = ofs;
 304             ofs = (ofs << 1) + 1;
 305             if ofs < last_ofs { ofs = max_ofs; } // uint overflow guard
 306         }
 307         if ofs > max_ofs { ofs = max_ofs; }
 308
 309         last_ofs += hint;
 310         ofs += hint;
 311     } else {
 312         let max_ofs = hint + 1;
 313         while ofs < max_ofs && *key <= array[hint-ofs] {
 314             last_ofs = ofs;
 315             ofs = (ofs << 1) + 1;
 316             if ofs < last_ofs { ofs = max_ofs; } // uint overflow guard
 317         }
 318
 319         if ofs > max_ofs { ofs = max_ofs; }
 320
 321         let tmp = last_ofs;
 322         last_ofs = hint - ofs;
 323         ofs = hint - tmp;
 324     }
 325     assert!((last_ofs < ofs || last_ofs+1 < ofs+1) && ofs <= size);
 326
 327     last_ofs += 1;
 328     while last_ofs < ofs {
 329         let m = last_ofs + ((ofs - last_ofs) >> 1);
 330         if *key > array[m] {
 331             last_ofs = m+1;
 332         } else {
 333             ofs = m;
 334         }
 335     }
 336     assert!(last_ofs == ofs);
 337     return ofs;
 338 }
 339
 340 fn gallop_right<T:Copy + Ord>(key: &const T,
 341                               array: &const [T],
 342                               hint: uint)
 343                            -> uint {
 344     let size = array.len();
 345     assert!(size != 0 && hint < size);
 346
 347     let mut last_ofs = 0;
 348     let mut ofs = 1;
 349
 350     if *key >= array[hint] {
 351         // Gallop right until array[hint+last_ofs] <= key < array[hint+ofs]
 352         let max_ofs = size - hint;
 353         while ofs < max_ofs && *key >= array[hint+ofs] {
 354             last_ofs = ofs;
 355             ofs = (ofs << 1) + 1;
 356             if ofs < last_ofs { ofs = max_ofs; }
 357         }
 358         if ofs > max_ofs { ofs = max_ofs; }
 359
 360         last_ofs += hint;
 361         ofs += hint;
 362     } else {
 363         // Gallop left until array[hint-ofs] <= key < array[hint-last_ofs]
 364         let max_ofs = hint + 1;
 365         while ofs < max_ofs && *key < array[hint-ofs] {
 366             last_ofs = ofs;
 367             ofs = (ofs << 1) + 1;
 368             if ofs < last_ofs { ofs = max_ofs; }
 369         }
 370         if ofs > max_ofs { ofs = max_ofs; }
 371
 372         let tmp = last_ofs;
 373         last_ofs = hint - ofs;
 374         ofs = hint - tmp;
 375     }
 376
 377     assert!((last_ofs < ofs || last_ofs+1 < ofs+1) && ofs <= size);
 378
 379     last_ofs += 1;
 380     while last_ofs < ofs {
 381         let m = last_ofs + ((ofs - last_ofs) >> 1);
 382
 383         if *key >= array[m] {
 384             last_ofs = m + 1;
 385         } else {
 386             ofs = m;
 387         }
 388     }
 389     assert!(last_ofs == ofs);
 390     return ofs;
 391 }
 392
 393 struct RunState {
 394     base: uint,
 395     len: uint,
 396 }
 397
 398 struct MergeState<T> {
 399     min_gallop: uint,
 400     runs: ~[RunState],
 401 }
 402
 403 // Fixme (#3853) Move into MergeState
 404 fn MergeState<T>() -> MergeState<T> {
 405     MergeState {
 406         min_gallop: MIN_GALLOP,
 407         runs: ~[],
 408     }
 409 }
 410
 411 impl<T:Copy + Ord> MergeState<T> {
 412     fn push_run(&mut self, run_base: uint, run_len: uint) {
 413         let tmp = RunState{base: run_base, len: run_len};
 414         self.runs.push(tmp);
 415     }
 416
 417     fn merge_at(&mut self, n: uint, array: &mut [T]) {
 418         let size = self.runs.len();
 419         assert!(size >= 2);
 420         assert!(n == size-2 || n == size-3);
 421
 422         let mut b1 = self.runs[n].base;
 423         let mut l1 = self.runs[n].len;
 424         let b2 = self.runs[n+1].base;
 425         let l2 = self.runs[n+1].len;
 426
 427         assert!(l1 > 0 && l2 > 0);
 428         assert!(b1 + l1 == b2);
 429
 430         self.runs[n].len = l1 + l2;
 431         if n == size-3 {
 432             self.runs[n+1].base = self.runs[n+2].base;
 433             self.runs[n+1].len = self.runs[n+2].len;
 434         }
 435
 436         let slice = vec::mut_slice(array, b1, b1+l1);
 437         let k = gallop_right(&const array[b2], slice, 0);
 438         b1 += k;
 439         l1 -= k;
 440         if l1 != 0 {
 441             let slice = vec::mut_slice(array, b2, b2+l2);
 442             let l2 = gallop_left(
 443                 &const array[b1+l1-1],slice,l2-1);
 444             if l2 > 0 {
 445                 if l1 <= l2 {
 446                     self.merge_lo(array, b1, l1, b2, l2);
 447                 } else {
 448                     self.merge_hi(array, b1, l1, b2, l2);
 449                 }
 450             }
 451         }
 452         self.runs.pop();
 453     }
 454
 455     fn merge_lo(&mut self, array: &mut [T], base1: uint, len1: uint,
 456                 base2: uint, len2: uint) {
 457         assert!(len1 != 0 && len2 != 0 && base1+len1 == base2);
 458
 459         let mut tmp = ~[];
 460         for uint::range(base1, base1+len1) |i| {
 461             tmp.push(array[i]);
 462         }
 463
 464         let mut c1 = 0;
 465         let mut c2 = base2;
 466         let mut dest = base1;
 467         let mut len1 = len1;
 468         let mut len2 = len2;
 469
 470         array[dest] <-> array[c2];
 471         dest += 1; c2 += 1; len2 -= 1;
 472
 473         if len2 == 0 {
 474             copy_vec(array, dest, tmp, 0, len1);
 475             return;
 476         }
 477         if len1 == 1 {
 478             copy_vec(array, dest, array, c2, len2);
 479             array[dest+len2] <-> tmp[c1];
 480             return;
 481         }
 482
 483         let mut min_gallop = self.min_gallop;
 484         loop {
 485             let mut count1 = 0;
 486             let mut count2 = 0;
 487             let mut break_outer = false;
 488
 489             loop {
 490                 assert!(len1 > 1 && len2 != 0);
 491                 if array[c2] < tmp[c1] {
 492                     array[dest] <-> array[c2];
 493                     dest += 1; c2 += 1; len2 -= 1;
 494                     count2 += 1; count1 = 0;
 495                     if len2 == 0 {
 496                         break_outer = true;
 497                     }
 498                 } else {
 499                     array[dest] <-> tmp[c1];
 500                     dest += 1; c1 += 1; len1 -= 1;
 501                     count1 += 1; count2 = 0;
 502                     if len1 == 1 {
 503                         break_outer = true;
 504                     }
 505                 }
 506                 if break_outer || ((count1 | count2) >= min_gallop) {
 507                     break;
 508                 }
 509             }
 510             if break_outer { break; }
 511
 512             // Start to gallop
 513             loop {
 514                 assert!(len1 > 1 && len2 != 0);
 515
 516                 let tmp_view = vec::const_slice(tmp, c1, c1+len1);
 517                 count1 = gallop_right(&const array[c2], tmp_view, 0);
 518                 if count1 != 0 {
 519                     copy_vec(array, dest, tmp, c1, count1);
 520                     dest += count1; c1 += count1; len1 -= count1;
 521                     if len1 <= 1 { break_outer = true; break; }
 522                 }
 523                 array[dest] <-> array[c2];
 524                 dest += 1; c2 += 1; len2 -= 1;
 525                 if len2 == 0 { break_outer = true; break; }
 526
 527                 let tmp_view = vec::const_slice(array, c2, c2+len2);
 528                 count2 = gallop_left(&const tmp[c1], tmp_view, 0);
 529                 if count2 != 0 {
 530                     copy_vec(array, dest, array, c2, count2);
 531                     dest += count2; c2 += count2; len2 -= count2;
 532                     if len2 == 0 { break_outer = true; break; }
 533                 }
 534                 array[dest] <-> tmp[c1];
 535                 dest += 1; c1 += 1; len1 -= 1;
 536                 if len1 == 1 { break_outer = true; break; }
 537                 min_gallop -= 1;
 538                 if !(count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
 539                     break;
 540                 }
 541             }
 542             if break_outer { break; }
 543             if min_gallop < 0 { min_gallop = 0; }
 544             min_gallop += 2; // Penalize for leaving gallop
 545         }
 546         self.min_gallop = if min_gallop < 1 { 1 } else { min_gallop };
 547
 548         if len1 == 1 {
 549             assert!(len2 > 0);
 550             copy_vec(array, dest, array, c2, len2);
 551             array[dest+len2] <-> tmp[c1];
 552         } else if len1 == 0 {
 553             fail!(~"Comparison violates its contract!");
 554         } else {
 555             assert!(len2 == 0);
 556             assert!(len1 > 1);
 557             copy_vec(array, dest, tmp, c1, len1);
 558         }
 559     }
 560
 561     fn merge_hi(&mut self, array: &mut [T], base1: uint, len1: uint,
 562                 base2: uint, len2: uint) {
 563         assert!(len1 != 1 && len2 != 0 && base1 + len1 == base2);
 564
 565         let mut tmp = ~[];
 566         for uint::range(base2, base2+len2) |i| {
 567             tmp.push(array[i]);
 568         }
 569
 570         let mut c1 = base1 + len1 - 1;
 571         let mut c2 = len2 - 1;
 572         let mut dest = base2 + len2 - 1;
 573         let mut len1 = len1;
 574         let mut len2 = len2;
 575
 576         array[dest] <-> array[c1];
 577         dest -= 1; c1 -= 1; len1 -= 1;
 578
 579         if len1 == 0 {
 580             copy_vec(array, dest-(len2-1), tmp, 0, len2);
 581             return;
 582         }
 583         if len2 == 1 {
 584             dest -= len1;
 585             c1 -= len1;
 586             copy_vec(array, dest+1, array, c1+1, len1);
 587             array[dest] <-> tmp[c2];
 588             return;
 589         }
 590
 591         let mut min_gallop = self.min_gallop;
 592         loop {
 593             let mut count1 = 0;
 594             let mut count2 = 0;
 595             let mut break_outer = false;
 596
 597             loop {
 598                 assert!(len1 != 0 && len2 > 1);
 599                 if tmp[c2] < array[c1] {
 600                     array[dest] <-> array[c1];
 601                     dest -= 1; c1 -= 1; len1 -= 1;
 602                     count1 += 1; count2 = 0;
 603                     if len1 == 0 {
 604                         break_outer = true;
 605                     }
 606                 } else {
 607                     array[dest] <-> tmp[c2];
 608                     dest -= 1; c2 -= 1; len2 -= 1;
 609                     count2 += 1; count1 = 0;
 610                     if len2 == 1 {
 611                         break_outer = true;
 612                     }
 613                 }
 614                 if break_outer || ((count1 | count2) >= min_gallop) {
 615                     break;
 616                 }
 617             }
 618             if break_outer { break; }
 619
 620             // Start to gallop
 621             loop {
 622                 assert!(len2 > 1 && len1 != 0);
 623
 624                 let tmp_view = vec::mut_slice(array, base1, base1+len1);
 625                 count1 = len1 - gallop_right(
 626                     &const tmp[c2], tmp_view, len1-1);
 627
 628                 if count1 != 0 {
 629                     dest -= count1; c1 -= count1; len1 -= count1;
 630                     copy_vec(array, dest+1, array, c1+1, count1);
 631                     if len1 == 0 { break_outer = true; break; }
 632                 }
 633
 634                 array[dest] <-> tmp[c2];
 635                 dest -= 1; c2 -= 1; len2 -= 1;
 636                 if len2 == 1 { break_outer = true; break; }
 637
 638                 let count2;
 639                 {
 640                     let tmp_view = vec::mut_slice(tmp, 0, len2);
 641                     count2 = len2 - gallop_left(&const array[c1],
 642                                                 tmp_view,
 643                                                 len2-1);
 644                     // Make tmp_view go out of scope to appease borrowck.
 645                 }
 646
 647                 if count2 != 0 {
 648                     dest -= count2; c2 -= count2; len2 -= count2;
 649                     copy_vec(array, dest+1, tmp, c2+1, count2);
 650                     if len2 <= 1 { break_outer = true; break; }
 651                 }
 652                 array[dest] <-> array[c1];
 653                 dest -= 1; c1 -= 1; len1 -= 1;
 654                 if len1 == 0 { break_outer = true; break; }
 655                 min_gallop -= 1;
 656                 if !(count1 >= MIN_GALLOP || count2 >= MIN_GALLOP) {
 657                     break;
 658                 }
 659             }
 660
 661             if break_outer { break; }
 662             if min_gallop < 0 { min_gallop = 0; }
 663             min_gallop += 2; // Penalize for leaving gallop
 664         }
 665         self.min_gallop = if min_gallop < 1 { 1 } else { min_gallop };
 666
 667         if len2 == 1 {
 668             assert!(len1 > 0);
 669             dest -= len1;
 670             c1 -= len1;
 671             copy_vec(array, dest+1, array, c1+1, len1);
 672             array[dest] <-> tmp[c2];
 673         } else if len2 == 0 {
 674             fail!(~"Comparison violates its contract!");
 675         } else {
 676             assert!(len1 == 0);
 677             assert!(len2 != 0);
 678             copy_vec(array, dest-(len2-1), tmp, 0, len2);
 679         }
 680     }
 681
 682     fn merge_collapse(&mut self, array: &mut [T]) {
 683         while self.runs.len() > 1 {
 684             let mut n = self.runs.len()-2;
 685             if n > 0 &&
 686                 self.runs[n-1].len <= self.runs[n].len + self.runs[n+1].len
 687             {
 688                 if self.runs[n-1].len < self.runs[n+1].len { n -= 1; }
 689             } else if self.runs[n].len <= self.runs[n+1].len {
 690                 /* keep going */
 691             } else {
 692                 break;
 693             }
 694             self.merge_at(n, array);
 695         }
 696     }
 697
 698     fn merge_force_collapse(&mut self, array: &mut [T]) {
 699         while self.runs.len() > 1 {
 700             let mut n = self.runs.len()-2;
 701             if n > 0 {
 702                 if self.runs[n-1].len < self.runs[n+1].len {
 703                     n -= 1;
 704                 }
 705             }
 706             self.merge_at(n, array);
 707         }
 708     }
 709 }
 710
 711 #[inline(always)]
 712 fn copy_vec<T:Copy>(dest: &mut [T],
 713                     s1: uint,
 714                     from: &const [T],
 715                     s2: uint,
 716                     len: uint) {
 717     assert!(s1+len <= dest.len() && s2+len <= from.len());
 718
 719     let mut slice = ~[];
 720     for uint::range(s2, s2+len) |i| {
 721         slice.push(from[i]);
 722     }
 723
 724     for slice.eachi |i, v| {
 725         dest[s1+i] = *v;
 726     }
 727 }
 728
 729 #[cfg(test)]
 730 mod test_qsort3 {
 731     use sort::*;
 732
 733     use core::vec;
 734
 735     fn check_sort(v1: &mut [int], v2: &mut [int]) {
 736         let len = vec::len::<int>(v1);
 737         quick_sort3::<int>(v1);
 738         let mut i = 0;
 739         while i < len {
 740             // debug!(v2[i]);
 741             assert!((v2[i] == v1[i]));
 742             i += 1;
 743         }
 744     }
 745
 746     #[test]
 747     fn test() {
 748         {
 749             let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
 750             let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
 751             check_sort(v1, v2);
 752         }
 753         {
 754             let mut v1 = ~[1, 1, 1];
 755             let mut v2 = ~[1, 1, 1];
 756             check_sort(v1, v2);
 757         }
 758         {
 759             let mut v1: ~[int] = ~[];
 760             let mut v2: ~[int] = ~[];
 761             check_sort(v1, v2);
 762         }
 763         { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
 764         {
 765             let mut v1 = ~[9, 3, 3, 3, 9];
 766             let mut v2 = ~[3, 3, 3, 9, 9];
 767             check_sort(v1, v2);
 768         }
 769     }
 770 }
 771
 772 #[cfg(test)]
 773 mod test_qsort {
 774     use sort::*;
 775
 776     use core::int;
 777     use core::vec;
 778
 779     fn check_sort(v1: &mut [int], v2: &mut [int]) {
 780         let len = vec::len::<int>(v1);
 781         fn leual(a: &int, b: &int) -> bool { *a <= *b }
 782         quick_sort::<int>(v1, leual);
 783         let mut i = 0u;
 784         while i < len {
 785             // debug!(v2[i]);
 786             assert!((v2[i] == v1[i]));
 787             i += 1;
 788         }
 789     }
 790
 791     #[test]
 792     fn test() {
 793         {
 794             let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
 795             let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
 796             check_sort(v1, v2);
 797         }
 798         {
 799             let mut v1 = ~[1, 1, 1];
 800             let mut v2 = ~[1, 1, 1];
 801             check_sort(v1, v2);
 802         }
 803         {
 804             let mut v1: ~[int] = ~[];
 805             let mut v2: ~[int] = ~[];
 806             check_sort(v1, v2);
 807         }
 808         { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
 809         {
 810             let mut v1 = ~[9, 3, 3, 3, 9];
 811             let mut v2 = ~[3, 3, 3, 9, 9];
 812             check_sort(v1, v2);
 813         }
 814     }
 815
 816     // Regression test for #750
 817     #[test]
 818     fn test_simple() {
 819         let mut names = ~[2, 1, 3];
 820
 821         let expected = ~[1, 2, 3];
 822
 823         do quick_sort(names) |x, y| { int::le(*x, *y) };
 824
 825         let immut_names = names;
 826
 827         let pairs = vec::zip_slice(expected, immut_names);
 828         for vec::each(pairs) |p| {
 829             let (a, b) = *p;
 830             debug!("%d %d", a, b);
 831             assert!((a == b));
 832         }
 833     }
 834 }
 835
 836 #[cfg(test)]
 837 mod tests {
 838
 839     use sort::*;
 840
 841     use core::vec;
 842
 843     fn check_sort(v1: &[int], v2: &[int]) {
 844         let len = vec::len::<int>(v1);
 845         pub fn le(a: &int, b: &int) -> bool { *a <= *b }
 846         let f = le;
 847         let v3 = merge_sort::<int>(v1, f);
 848         let mut i = 0u;
 849         while i < len {
 850             debug!(v3[i]);
 851             assert!((v3[i] == v2[i]));
 852             i += 1;
 853         }
 854     }
 855
 856     #[test]
 857     fn test() {
 858         {
 859             let v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
 860             let v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
 861             check_sort(v1, v2);
 862         }
 863         { let v1 = ~[1, 1, 1]; let v2 = ~[1, 1, 1]; check_sort(v1, v2); }
 864         { let v1:~[int] = ~[]; let v2:~[int] = ~[]; check_sort(v1, v2); }
 865         { let v1 = ~[9]; let v2 = ~[9]; check_sort(v1, v2); }
 866         {
 867             let v1 = ~[9, 3, 3, 3, 9];
 868             let v2 = ~[3, 3, 3, 9, 9];
 869             check_sort(v1, v2);
 870         }
 871     }
 872
 873     #[test]
 874     fn test_merge_sort_mutable() {
 875         pub fn le(a: &int, b: &int) -> bool { *a <= *b }
 876         let mut v1 = ~[3, 2, 1];
 877         let v2 = merge_sort(v1, le);
 878         assert!(v2 == ~[1, 2, 3]);
 879     }
 880
 881     #[test]
 882     fn test_merge_sort_stability() {
 883         // tjc: funny that we have to use parens
 884         fn ile(x: &(&'static str), y: &(&'static str)) -> bool
 885         {
 886             // FIXME: #4318 Instead of to_ascii and to_str_ascii, could use
 887             // to_ascii_consume and to_str_consume to not do a unnecessary copy.
 888             // (Actually, could just remove the to_str_* call, but needs an deriving(Ord) on
 889             // Ascii)
 890             let x = x.to_ascii().to_lower().to_str_ascii();
 891             let y = y.to_ascii().to_lower().to_str_ascii();
 892             x <= y
 893         }
 894
 895         let names1 = ~["joe bob", "Joe Bob", "Jack Brown", "JOE Bob",
 896                        "Sally Mae", "JOE BOB", "Alex Andy"];
 897         let names2 = ~["Alex Andy", "Jack Brown", "joe bob", "Joe Bob",
 898                        "JOE Bob", "JOE BOB", "Sally Mae"];
 899         let names3 = merge_sort(names1, ile);
 900         assert!(names3 == names2);
 901     }
 902 }
 903
 904 #[cfg(test)]
 905 mod test_tim_sort {
 906     use sort::tim_sort;
 907     use core::rand::RngUtil;
 908
 909     struct CVal {
 910         val: float,
 911     }
 912
 913     impl Ord for CVal {
 914         fn lt(&self, other: &CVal) -> bool {
 915             let rng = rand::rng();
 916             if rng.gen::<float>() > 0.995 { fail!(~"It's happening!!!"); }
 917             (*self).val < other.val
 918         }
 919         fn le(&self, other: &CVal) -> bool { (*self).val <= other.val }
 920         fn gt(&self, other: &CVal) -> bool { (*self).val > other.val }
 921         fn ge(&self, other: &CVal) -> bool { (*self).val >= other.val }
 922     }
 923
 924     fn check_sort(v1: &mut [int], v2: &mut [int]) {
 925         let len = vec::len::<int>(v1);
 926         tim_sort::<int>(v1);
 927         let mut i = 0u;
 928         while i < len {
 929             // debug!(v2[i]);
 930             assert!((v2[i] == v1[i]));
 931             i += 1u;
 932         }
 933     }
 934
 935     #[test]
 936     fn test() {
 937         {
 938             let mut v1 = ~[3, 7, 4, 5, 2, 9, 5, 8];
 939             let mut v2 = ~[2, 3, 4, 5, 5, 7, 8, 9];
 940             check_sort(v1, v2);
 941         }
 942         {
 943             let mut v1 = ~[1, 1, 1];
 944             let mut v2 = ~[1, 1, 1];
 945             check_sort(v1, v2);
 946         }
 947         {
 948             let mut v1: ~[int] = ~[];
 949             let mut v2: ~[int] = ~[];
 950             check_sort(v1, v2);
 951         }
 952         { let mut v1 = ~[9]; let mut v2 = ~[9]; check_sort(v1, v2); }
 953         {
 954             let mut v1 = ~[9, 3, 3, 3, 9];
 955             let mut v2 = ~[3, 3, 3, 9, 9];
 956             check_sort(v1, v2);
 957         }
 958     }
 959
 960     #[test]
 961     #[should_fail]
 962     #[cfg(unix)]
 963     fn crash_test() {
 964         let rng = rand::rng();
 965         let mut arr = do vec::from_fn(1000) |_i| {
 966             CVal { val: rng.gen() }
 967         };
 968
 969         tim_sort(arr);
 970         fail!(~"Guarantee the fail");
 971     }
 972
 973     struct DVal { val: uint }
 974
 975     impl Ord for DVal {
 976         fn lt(&self, _x: &DVal) -> bool { true }
 977         fn le(&self, _x: &DVal) -> bool { true }
 978         fn gt(&self, _x: &DVal) -> bool { true }
 979         fn ge(&self, _x: &DVal) -> bool { true }
 980     }
 981
 982     #[test]
 983     fn test_bad_Ord_impl() {
 984         let rng = rand::rng();
 985         let mut arr = do vec::from_fn(500) |_i| {
 986             DVal { val: rng.gen() }
 987         };
 988
 989         tim_sort(arr);
 990     }
 991 }
 992
 993 #[cfg(test)]
 994 mod big_tests {
 995     use sort::*;
 996     use core::rand::RngUtil;
 997
 998     #[test]
 999     fn test_unique() {
1000         let low = 5;
1001         let high = 10;
1002         tabulate_unique(low, high);
1003     }
1004
1005     #[test]
1006     fn test_managed() {
1007         let low = 5;
1008         let high = 10;
1009         tabulate_managed(low, high);
1010     }
1011
1012     fn multiplyVec<T:Copy>(arr: &const [T], num: uint) -> ~[T] {
1013         let size = arr.len();
1014         let res = do vec::from_fn(num) |i| {
1015             arr[i % size]
1016         };
1017         res
1018     }
1019
1020     fn makeRange(n: uint) -> ~[uint] {
1021         let one = do vec::from_fn(n) |i| { i };
1022         let mut two = copy one;
1023         vec::reverse(two);
1024         vec::append(two, one)
1025     }
1026
1027     fn tabulate_unique(lo: uint, hi: uint) {
1028         fn isSorted<T:Ord>(arr: &const [T]) {
1029             for uint::range(0, arr.len()-1) |i| {
1030                 if arr[i] > arr[i+1] {
1031                     fail!(~"Array not sorted");
1032                 }
1033             }
1034         }
1035
1036         let rng = rand::rng();
1037
1038         for uint::range(lo, hi) |i| {
1039             let n = 1 << i;
1040             let mut arr: ~[float] = do vec::from_fn(n) |_i| {
1041                 rng.gen()
1042             };
1043
1044             tim_sort(arr); // *sort
1045             isSorted(arr);
1046
1047             vec::reverse(arr);
1048             tim_sort(arr); // \sort
1049             isSorted(arr);
1050
1051             tim_sort(arr); // /sort
1052             isSorted(arr);
1053
1054             for 3.times {
1055                 let i1 = rng.gen_uint_range(0, n);
1056                 let i2 = rng.gen_uint_range(0, n);
1057                 arr[i1] <-> arr[i2];
1058             }
1059             tim_sort(arr); // 3sort
1060             isSorted(arr);
1061
1062             if n >= 10 {
1063                 let size = arr.len();
1064                 let mut idx = 1;
1065                 while idx <= 10 {
1066                     arr[size-idx] = rng.gen();
1067                     idx += 1;
1068                 }
1069             }
1070             tim_sort(arr); // +sort
1071             isSorted(arr);
1072
1073             for (n/100).times {
1074                 let idx = rng.gen_uint_range(0, n);
1075                 arr[idx] = rng.gen();
1076             }
1077             tim_sort(arr);
1078             isSorted(arr);
1079
1080             let mut arr = if n > 4 {
1081                 let part = vec::slice(arr, 0, 4);
1082                 multiplyVec(part, n)
1083             } else { arr };
1084             tim_sort(arr); // ~sort
1085             isSorted(arr);
1086
1087             let mut arr = vec::from_elem(n, -0.5);
1088             tim_sort(arr); // =sort
1089             isSorted(arr);
1090
1091             let half = n / 2;
1092             let mut arr = makeRange(half).map(|i| *i as float);
1093             tim_sort(arr); // !sort
1094             isSorted(arr);
1095         }
1096     }
1097
1098     fn tabulate_managed(lo: uint, hi: uint) {
1099         fn isSorted<T:Ord>(arr: &const [@T]) {
1100             for uint::range(0, arr.len()-1) |i| {
1101                 if arr[i] > arr[i+1] {
1102                     fail!(~"Array not sorted");
1103                 }
1104             }
1105         }
1106
1107         let rng = rand::rng();
1108
1109         for uint::range(lo, hi) |i| {
1110             let n = 1 << i;
1111             let arr: ~[@float] = do vec::from_fn(n) |_i| {
1112                 @rng.gen()
1113             };
1114             let mut arr = arr;
1115
1116             tim_sort(arr); // *sort
1117             isSorted(arr);
1118
1119             vec::reverse(arr);
1120             tim_sort(arr); // \sort
1121             isSorted(arr);
1122
1123             tim_sort(arr); // /sort
1124             isSorted(arr);
1125
1126             for 3.times {
1127                 let i1 = rng.gen_uint_range(0, n);
1128                 let i2 = rng.gen_uint_range(0, n);
1129                 arr[i1] <-> arr[i2];
1130             }
1131             tim_sort(arr); // 3sort
1132             isSorted(arr);
1133
1134             if n >= 10 {
1135                 let size = arr.len();
1136                 let mut idx = 1;
1137                 while idx <= 10 {
1138                     arr[size-idx] = @rng.gen();
1139                     idx += 1;
1140                 }
1141             }
1142             tim_sort(arr); // +sort
1143             isSorted(arr);
1144
1145             for (n/100).times {
1146                 let idx = rng.gen_uint_range(0, n);
1147                 arr[idx] = @rng.gen();
1148             }
1149             tim_sort(arr);
1150             isSorted(arr);
1151
1152             let mut arr = if n > 4 {
1153                 let part = vec::slice(arr, 0, 4);
1154                 multiplyVec(part, n)
1155             } else { arr };
1156             tim_sort(arr); // ~sort
1157             isSorted(arr);
1158
1159             let mut arr = vec::from_elem(n, @(-0.5));
1160             tim_sort(arr); // =sort
1161             isSorted(arr);
1162
1163             let half = n / 2;
1164             let mut arr = makeRange(half).map(|i| @(*i as float));
1165             tim_sort(arr); // !sort
1166             isSorted(arr);
1167         }
1168     }
1169
1170     struct LVal<'self> {
1171         val: uint,
1172         key: &'self fn(@uint),
1173     }
1174
1175     #[unsafe_destructor]
1176     impl<'self> Drop for LVal<'self> {
1177         fn finalize(&self) {
1178             let x = unsafe { task::local_data::local_data_get(self.key) };
1179             match x {
1180                 Some(@y) => {
1181                     unsafe {
1182                         task::local_data::local_data_set(self.key, @(y+1));
1183                     }
1184                 }
1185                 _ => fail!(~"Expected key to work"),
1186             }
1187         }
1188     }
1189
1190     impl<'self> Ord for LVal<'self> {
1191         fn lt<'a>(&self, other: &'a LVal<'self>) -> bool {
1192             (*self).val < other.val
1193         }
1194         fn le<'a>(&self, other: &'a LVal<'self>) -> bool {
1195             (*self).val <= other.val
1196         }
1197         fn gt<'a>(&self, other: &'a LVal<'self>) -> bool {
1198             (*self).val > other.val
1199         }
1200         fn ge<'a>(&self, other: &'a LVal<'self>) -> bool {
1201             (*self).val >= other.val
1202         }
1203     }
1204 }
1205
1206 // Local Variables:
1207 // mode: rust;
1208 // fill-column: 78;
1209 // indent-tabs-mode: nil
1210 // c-basic-offset: 4
1211 // buffer-file-coding-system: utf-8-unix
1212 // End: