algostru 0.4.0

Algorithms (algo) and Data Structures (stru)
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

use crate::collections::vec_range_midpoint;

/// Merge Vectors
///
/// Input: two sorted vectors x and y
/// Output: merged vector containing the elements of x and y
///
/// =================================================================================================
///
/// result = new vector
/// x_index = 0
/// y_index = 0
///
/// while index_x < length of x and index_y < length of y
///     result.push smaller of x[x_index] and y[y_index]
///     increment index for smaller of x[x_index] and y[y_index] respectively
///
/// result.push for all elements remaining in x or y
///
/// return result
fn merge(x: Vec<isize>, y: Vec<isize>) -> Vec<isize> {
    let mut merged: Vec<isize> = Vec::new();
    let mut x_index = 0;
    let mut y_index = 0;

    while x_index < x.len() && y_index < y.len() {
        if x[x_index] <= y[y_index] {
            merged.push(x[x_index]);
            x_index += 1;
        } else {
            merged.push(y[y_index]);
            y_index += 1;
        }
    }

    for element in x[x_index..].to_vec() {
        merged.push(element);
    }
    for element in y[y_index..].to_vec() {
        merged.push(element);
    }

    merged
}

/// Merge Sort
///
/// Input: vector x of n elements
/// Output: sorted vector of n elements
///
/// ================================================================================================
///
/// if x length equals 0 or 1 then
///     base case: return vector x
///
/// recursive sort:
///   a = merge sort of first halve of x
///   b = merge sort of second halve of x
///
/// return result: vector x sorted
pub fn sort(x: Vec<isize>) -> Vec<isize> {
    if x.len() <= 1 {
        return x;
    }

    let midpoint = vec_range_midpoint(&x);
    let a = &x[..midpoint];
    let b = &x[midpoint..];

    let c = sort(a.to_vec());
    let d = sort(b.to_vec());

    merge(c, d)
}