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