sort_it/algorithms/
merge_sort.rs

1use std::time::{ Instant, Duration };
2
3/// A trait providing the merge sort method.
4pub trait MergeSort<T: PartialEq + PartialOrd + Clone + Copy> {
5    /// The merge sort algorithm.
6    /// 
7    /// Sorts the `Vec` it is called on.
8    fn merge_sort(&mut self);
9
10    /// The merge sort algorithm but timed.
11    /// 
12    /// Sorts the `Vec` it is called on and returns the `Duration` of the process.
13    fn merge_sort_timed(&mut self) -> Duration;
14
15    /// The merge sort algorithm but stepped.
16    /// 
17    /// Sorts the `Vec` it is called on and returns a `Vec` containing each step of the process.
18    fn merge_sort_stepped(&mut self) -> Vec<Vec<T>>;
19
20    /// The merge sort algorithm but stepped _and_ timed.
21    /// 
22    /// Sorts the `Vec` it is called on and returns a `Vec` containing each step of the process, 
23    /// including the `Duration` of the entire process.
24    fn merge_sort_stepped_and_timed(&mut self) -> (Vec<Vec<T>>, Duration);
25}
26
27/// The trait implementation of the merge sort algorithm.
28impl<T> MergeSort<T> for Vec<T> 
29    where T: PartialEq + PartialOrd + Clone + Copy,
30{
31    fn merge_sort(&mut self) {
32        // If the array only contains one element, it's sorted by default.
33        if self.len() <= 1 {
34            return;
35        }
36
37        // Obtain the right- and left-hand-sides.
38        let rhs = &self[..self.len()/2];
39        let lhs = &self[self.len()/2..];
40
41        *self = merge_rec(rhs.to_vec(), lhs.to_vec());
42    }
43
44    fn merge_sort_timed(&mut self) -> Duration {
45        let time = Instant::now();
46
47        // If the array only contains one element, it's sorted by default.
48        if self.len() <= 1 {
49            return time.elapsed();
50        }
51
52        // Obtain the right- and left-hand-sides.
53        let rhs = &self[..self.len()/2];
54        let lhs = &self[self.len()/2..];
55
56        *self = merge_rec(rhs.to_vec(), lhs.to_vec());
57
58        return time.elapsed();
59    }
60
61    fn merge_sort_stepped(&mut self) -> Vec<Vec<T>> {
62        let mut steps = vec![self.clone()];
63
64        // If the array only contains one element, it's sorted by default.
65        if self.len() <= 1 {
66            return steps;
67        }
68
69        // Obtain the right- and left-hand-sides.
70        let rhs = &self[..self.len()/2];
71        let lhs = &self[self.len()/2..];
72
73        *self = merge_rec_stepped(rhs.to_vec(), lhs.to_vec(), &mut steps);
74
75        return steps;
76    }
77
78    fn merge_sort_stepped_and_timed(&mut self) -> (Vec<Vec<T>>, Duration) {
79        let time = Instant::now();
80
81        let mut steps = vec![self.clone()];
82
83        // If the array only contains one element, it's sorted by default.
84        if self.len() <= 1 {
85            return (steps, time.elapsed());
86        }
87
88        // Obtain the right- and left-hand-sides.
89        let rhs = &self[..self.len()/2];
90        let lhs = &self[self.len()/2..];
91
92        *self = merge_rec_stepped(rhs.to_vec(), lhs.to_vec(), &mut steps);
93
94        (steps, time.elapsed())
95    }
96}
97
98/// The merge sort algorithm.
99/// 
100/// Sorts the given `Vec` and returns the result.
101pub fn merge_sort<T>(arr: Vec<T>) -> Vec<T> 
102    where T: PartialEq + PartialOrd + Clone + Copy,
103{
104    // If the array only contains one element, it's sorted by default.
105    if arr.len() <= 1 {
106        return arr;
107    }
108
109    // Obtain the right- and left-hand-sides.
110    let rhs = &arr[..arr.len()/2];
111    let lhs = &arr[arr.len()/2..];
112
113    merge_rec(rhs.to_vec(), lhs.to_vec())
114}
115
116/// The merge sort algorithm but timed.
117///
118/// Sorts the given `Vec` and returns the result and the `Duration` of the process.
119pub fn merge_sort_timed<T>(arr: Vec<T>) -> (Vec<T>, Duration) 
120    where T: PartialEq + PartialOrd + Clone + Copy,
121{
122    let time = Instant::now();
123
124    // If the array only contains one element, it's sorted by default.
125    if arr.len() <= 1 {
126        return (arr, time.elapsed());
127    }
128
129    // Obtain the right- and left-hand-sides.
130    let rhs = &arr[..arr.len()/2];
131    let lhs = &arr[arr.len()/2..];
132
133    (merge_rec(rhs.to_vec(), lhs.to_vec()), time.elapsed())
134}
135
136/// The merge sort algorithm but stepped.
137///
138/// Sorts the given `Vec` and returns the result and a `Vec` containing all the steps of the entire 
139/// process.
140pub fn merge_sort_stepped<T>(arr: Vec<T>) -> (Vec<T>, Vec<Vec<T>>)
141    where T: PartialEq + PartialOrd + Clone + Copy,
142{
143    let mut steps = vec![arr.clone()];
144
145    // If the array only contains one element, it's sorted by default.
146    if arr.len() <= 1 {
147        return (arr, steps);
148    }
149
150    // Obtain the right- and left-hand-sides.
151    let rhs = &arr[..arr.len()/2];
152    let lhs = &arr[arr.len()/2..];
153
154    let sorted = merge_rec_stepped(rhs.to_vec(), lhs.to_vec(), &mut steps);
155
156    (sorted, steps)
157}
158
159/// The merge sort algorithm but stepped _and_ timed.
160///
161/// Sorts the given `Vec` and returns the result and a `Vec` containing all the steps of the
162/// process, including the `Duration` of the entire process.
163pub fn merge_sort_stepped_and_timed<T>(arr: Vec<T>) -> (Vec<T>, Vec<Vec<T>>, Duration) 
164    where T: PartialEq + PartialOrd + Clone + Copy,
165{
166    let time = Instant::now();
167
168    let mut steps = vec![arr.clone()];
169
170    // If the array only contains one element, it's sorted by default.
171    if arr.len() <= 1 {
172        return (arr, steps, time.elapsed());
173    }
174
175    // Obtain the right- and left-hand-sides.
176    let rhs = &arr[..arr.len()/2];
177    let lhs = &arr[arr.len()/2..];
178
179    let sorted = merge_rec_stepped(rhs.to_vec(), lhs.to_vec(), &mut steps);
180
181    (sorted, steps, time.elapsed())
182}
183
184/// Auxiliary merge function.
185fn merge_rec<T>(mut rhs: Vec<T>, mut lhs: Vec<T>) -> Vec<T> 
186    where T: PartialEq + PartialOrd + Clone + Copy,
187{
188    let mut sorted = vec![];
189
190    if rhs.len() > 1 {
191        let new_rhs = &rhs[..rhs.len()/2];
192        let new_lhs = &rhs[rhs.len()/2..];
193
194        rhs = merge_rec(new_rhs.to_vec(), new_lhs.to_vec());
195    }
196    if lhs.len() > 1 {
197        let new_rhs = &lhs[..lhs.len()/2];
198        let new_lhs = &lhs[lhs.len()/2..];
199
200        lhs = merge_rec(new_rhs.to_vec(), new_lhs.to_vec());
201    }
202
203    let mut i = 0;
204    let mut j = 0;
205
206    while i < rhs.len() && j < lhs.len() {
207        if rhs[i] <= lhs[j] {
208            sorted.push(rhs[i]);
209            i += 1;
210        } else {
211            sorted.push(lhs[j]);
212            j += 1;
213        }
214    }
215
216    if i == rhs.len() {
217        for k in j..lhs.len() {
218            sorted.push(lhs[k]);
219        }
220    } else if j == lhs.len() {
221        for k in i..rhs.len() {
222            sorted.push(rhs[k]);
223        }
224    }
225
226    return sorted;
227}
228
229/// Auxiliary merge function with step support.
230fn merge_rec_stepped<T>(mut rhs: Vec<T>, mut lhs: Vec<T>, steps: &mut Vec<Vec<T>>) -> Vec<T> 
231    where T: PartialEq + PartialOrd + Clone + Copy,
232{
233    let mut sorted = vec![];
234
235    if rhs.len() > 1 {
236        let new_rhs = &rhs[..rhs.len()/2];
237        let new_lhs = &rhs[rhs.len()/2..];
238
239        rhs = merge_rec_stepped(new_rhs.to_vec(), new_lhs.to_vec(), steps);
240    }
241    if lhs.len() > 1 {
242        let new_rhs = &lhs[..lhs.len()/2];
243        let new_lhs = &lhs[lhs.len()/2..];
244
245        lhs = merge_rec_stepped(new_rhs.to_vec(), new_lhs.to_vec(), steps);
246    }
247
248    let mut i = 0;
249    let mut j = 0;
250
251    while i < rhs.len() && j < lhs.len() {
252        if rhs[i] <= lhs[j] {
253            sorted.push(rhs[i]);
254            i += 1;
255        } else {
256            sorted.push(lhs[j]);
257            j += 1;
258        }
259    }
260
261    if i == rhs.len() {
262        for k in j..lhs.len() {
263            sorted.push(lhs[k]);
264        }
265    } else if j == lhs.len() {
266        for k in i..rhs.len() {
267            sorted.push(rhs[k]);
268        }
269    }
270
271    steps.push(sorted.clone());
272
273    return sorted;
274}
sort_it/algorithms/merge_sort.rs

sort_it/algorithms/
merge_sort.rs
