4
\$\begingroup\$

I'm in the process of learning both Rust and algorithms after primarily focusing on web development. As such I've had a go at implementing merge sort both iteratively and recursively.

I've looked for various implementations in Rust online and found them either to be quite complex, quite specific (for types/use-cases) or quite hard to reason the flow of logic through - although MergeSort in Rust and the comment by Zeta proved to be very useful!

Both implementations appear to be passing all the test cases, however if anyone is able to provide me with any feedback/pointers on how to improve/optimise the algorithms (or any missed test scenarios) it would be greatly appreciated.

I'm particularly interested in ensuring both would have O(nlog(n)) time complexity - which I think the recursive one would, but I'm not so sure about the iterative one?

Recursive Merge Sort

pub fn recursive_merge_sort<T>(collection: &mut [T])
where
    T: Ord + Copy,
{
    if collection.len() > 1 {
        let (lhs, rhs) = collection.split_at_mut(collection.len() / 2);
        recursive_merge_sort(lhs);
        recursive_merge_sort(rhs);
        merge(collection, collection.len())
    }
}

Iterative Merge Sort

pub fn iterative_merge_sort<T>(collection: &mut [T])
where
    T: Ord + Copy,
{
    let length = collection.len();
    if length <= 1 {
        return;
    }

    let mut current_sub_array_multiplier = 1;
    let mut current_sub_array_size = 2;

    loop {
        collection
            .chunks_mut(current_sub_array_size)
            .for_each(|sub_arr| merge(sub_arr, current_sub_array_size));

        if current_sub_array_size > length {
            break;
        }

        current_sub_array_multiplier += 1;
        current_sub_array_size = 2f64.powi(current_sub_array_multiplier) as usize;
    }
}

Merge Function

pub fn merge<T>(collection: &mut [T], sub_array_length: usize)
where
    T: Ord + Copy,
{
    if sub_array_length < 2 {
        return;
    }

    let mut temp_vec = Vec::with_capacity(collection.len());
    {
        let mid = sub_array_length / 2;
        let mut lhs = collection.iter().take(mid).peekable();
        let mut rhs = collection.iter().skip(mid).peekable();

        while let (Some(&lhs_el), Some(&rhs_el)) = (lhs.peek(), rhs.peek()) {
            if *lhs_el <= *rhs_el {
                temp_vec.push(*lhs.next().unwrap())
            } else {
                temp_vec.push(*rhs.next().unwrap())
            }
        }

        for el in lhs {
            temp_vec.push(*el);
        }

        for el in rhs {
            temp_vec.push(*el);
        }
    }

    assert_eq!(temp_vec.len(), collection.len());
    temp_vec
        .iter()
        .enumerate()
        .for_each(|(i, el)| collection[i] = *el);
}

Sample Test cases:

#[cfg(test)]
mod recursive_tests {
    use super::*;

    #[test]
    fn test_semi_sorted() {
        let mut arr = vec![1, 23, 2, 32, 29, 33];
        recursive_merge_sort(&mut arr);
        assert_eq!(arr, [1, 2, 23, 29, 32, 33]);
    }

    #[test]
    fn test_backwards() {
        let mut arr = vec![50, 25, 10, 5, 1];
        recursive_merge_sort(&mut arr);
        assert_eq!(arr, [1, 5, 10, 25, 50]);
    }

    #[test]
    fn test_sorted() {
        let mut arr = vec![1, 5, 10, 25, 50];
        recursive_merge_sort(&mut arr);
        assert_eq!(arr, [1, 5, 10, 25, 50]);
    }

    #[test]
    fn test_empty() {
        let mut arr: Vec<u32> = vec![];
        recursive_merge_sort(&mut arr);
        assert_eq!(arr, []);
    }

    #[test]
    fn test_len_two() {
        let mut arr = vec![5, 1];
        recursive_merge_sort(&mut arr);
        assert_eq!(arr, [1, 5]);
    }

    #[test]
    fn test_partially_sorted() {
        let mut arr = vec![50, 75, 1, 1, 3, 4, 5, 6, 50];
        recursive_merge_sort(&mut arr);
        assert_eq!(arr, [1, 1, 3, 4, 5, 6, 50, 50, 75]);
    }
}

```
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.