sorting-algorithm 0.1.17

An implementation of various sorting algorithms
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

/// Sorts a data set using Merge Sort
///
/// Average time complexity: O(n logn)
///
/// # Example
///
/// ```
/// use sorting_algorithm::merge_sort;
///
/// fn main() {
///     let mut data = [3, 1, 2, 5, 4];
///     
///     merge_sort::sort(&mut data);
///
///     assert_eq!(data, [1, 2, 3, 4, 5]);
/// }
/// ```
pub fn sort<T: Ord + Clone>(data: &mut [T]) {
    if data.len() > 1 {
        let mid = data.len() / 2;

        sort(&mut data[..mid]);
        sort(&mut data[mid..]);

        merge(data, mid);
    }
}

fn merge<T: Ord + Clone>(data: &mut [T], mid: usize) {
    let left = data[..mid].to_vec();
    let right = &data[mid..].to_vec();

    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] < right[j] {
            data[k] = left[i].clone();
            i += 1
        } else {
            data[k] = right[j].clone();
            j += 1
        }

        k += 1;
    }

    while i < left.len() {
        data[k] = left[i].clone();
        i += 1;
        k += 1;
    }

    while j < right.len() {
        data[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}