timsort 0.1.3

Rust implementation of the modified MergeSort used in Python and Java
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

use crate::{comparator, never, ord_t_comparator};

#[test]
fn empty() {
    let list: Vec<usize> = vec![];
    let (ord, len) = find_run(&list);
    assert_eq!(ord, false);
    assert_eq!(len, 0);
}

#[test]
fn single() {
    let (ord, len) = find_run(&[1]);
    assert_eq!(ord, false);
    assert_eq!(len, 1);
}

#[test]
fn greater() {
    let (ord, len) = find_run(&[1, 2, 2, 3, 4, 5]);
    assert_eq!(ord, false);
    assert_eq!(len, 6);
}

// Note: I used to have a version that would allow sub-runs of equal elements in a
// less ordering. Unfortunately, reversing those sub-runs creates an unstable sort.
#[test]
fn less_stable() {
    let (ord, len) = find_run(&[5, 4, 4, 3, 4, 5]);
    assert_eq!(ord, true);
    assert_eq!(len, 2);
}

#[test]
fn less() {
    let (ord, len) = find_run(&[5, 4, 3, 2, 1, 0]);
    assert_eq!(ord, true);
    assert_eq!(len, 6);
}

#[test]
fn equal() {
    let (ord, len) = find_run(&[2, 2, 2, 2, 2, 2]);
    assert_eq!(ord, false);
    assert_eq!(len, 6);
}

#[test]
fn get_run_reverse() {
    let mut list = vec![7, 6, 5, 4, 3, 3];
    let len = get_run(&mut list);
    assert_eq!(len, 5);
    assert_eq!(list[0], 3);
    assert_eq!(list[1], 4);
    assert_eq!(list[2], 5);
    assert_eq!(list[3], 6);
    assert_eq!(list[4], 7);
}

#[test]
fn get_run_noreverse() {
    let mut list = vec![3, 4, 5, 6, 7, 3];
    let len = get_run(&mut list);
    assert_eq!(len, 5);
    assert_eq!(list[0], 3);
    assert_eq!(list[1], 4);
    assert_eq!(list[2], 5);
    assert_eq!(list[3], 6);
    assert_eq!(list[4], 7);
}

/// With comparator.
fn find_run<T: Ord>(list: &[T]) -> (bool, usize) {
    super::find_run(list, &comparator(|a, b| Ok(a > b))).unwrap_or_else(never)
}

/// With comparator.
fn get_run<T: Ord>(list: &mut [T]) -> usize {
    super::get_run(list, &ord_t_comparator()).unwrap_or_else(never)
}