-
Notifications
You must be signed in to change notification settings - Fork 1
/
tim_sort.rs
140 lines (119 loc) · 3.67 KB
/
tim_sort.rs
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
use std::cmp;
/// Insertion Sort with left/right index boundaries
fn insertion_sort(x: &mut Vec<isize>, left: usize, right: Option<usize>) {
let right = match right {
Some(right) => right,
_ => x.len()
};
for i in left..right {
let mut insert_index = i;
let current_value = x[insert_index];
while insert_index > left && x[insert_index - 1] > current_value {
x[insert_index] = x[insert_index - 1];
insert_index -= 1;
}
x[insert_index] = current_value;
}
}
/// Merge Sort by reference with left/right sides (x/y)
fn merge(x: &mut Vec<isize>, start: usize, midpoint: usize, end: usize) {
let mut sorted: Vec<isize> = Vec::new();
let mut start = start;
let mut midpoint = midpoint;
if midpoint >= end {
midpoint = start;
start = 0;
}
let left = &x[start..midpoint];
let right = &x[midpoint..end];
let mut left_index = 0;
let mut right_index = 0;
while left_index < left.len() && right_index < right.len() {
if left[left_index] <= right[right_index] {
sorted.push(left[left_index]);
left_index += 1;
} else {
sorted.push(right[right_index]);
right_index += 1;
}
}
while left_index < left.len() {
sorted.push(left[left_index]);
left_index += 1;
}
while right_index < right.len() {
sorted.push(right[right_index]);
right_index += 1;
}
let mut index_start = start;
for element in sorted.iter() {
x[index_start] = *element;
index_start += 1;
}
}
/// Time Sort
///
/// Input: mutable reference of vector x of n elements
/// Post-condition: sorted vector of n elements
///
/// ================================================================================================
///
/// ```ignore
/// set chunk size for iterative sorting
/// set n to unsorted vector size
///
/// iterate over chunks
/// call insertion sort on each chunk
///
/// set size to chunk size
/// while size is less than length of vector
/// for each size * 2 (start after left/right chunk size)
/// set midpoint to start plus size
/// set end to minimum of start plus size * 2 or length of vector
///
/// merge two left/right chunks
///
/// size = size * 2
/// ```
pub fn sort(x: &mut Vec<isize>) {
let chunk_size = 32;
let n = x.len();
for i in (0..n).step_by(chunk_size) {
insertion_sort(x, i, Some(cmp::min(i + chunk_size, n)));
}
let mut size = chunk_size;
while size < n {
for start in (0..n).step_by(size * 2) {
let midpoint = start + size;
let end = cmp::min(start + size * 2, n);
merge(x, start, midpoint, end);
}
size *= 2;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_insertion_sort_with_total_boundaries() {
let mut x: Vec<isize> = vec![
10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
];
let expectation: Vec<isize> = vec![
-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
];
insertion_sort(&mut x, 0, None);
assert_eq!(x, expectation);
}
#[test]
fn test_insertion_sort_with_subset_boundaries() {
let mut x: Vec<isize> = vec![
10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10
];
let expectation: Vec<isize> = vec![
10, 9, 8, 7, 6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, -6, -7, -8, -9, -10
];
insertion_sort(&mut x, 5, Some(16));
assert_eq!(x, expectation);
}
}