merge_sort.rs

pub fn merge_no_sentinel<T: Clone + Ord>(
    a: &mut [T],
    p: usize,
    q: usize,
    r: usize,
) -> Result<(), Error> {
    if !(p <= q && q <= r && r < a.len()) {
        return Err(PQROutOfBounds(p, q, r).into());
    }

    let left = a[p..q].to_vec();
    let right = a[q..=r].to_vec();

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

    for mut k in p..=r {
        if i >= left.len() {
            for item in &right[j..] {
                a[k] = item.clone();
                k += 1;
            }
            break;
        }

        if j >= right.len() {
            for item in &left[i..] {
                a[k] = item.clone();
                k += 1;
            }
            break;
        }

        if left[i] <= right[j] {
            a[k] = left[i].clone();

            i += 1;
        } else {
            a[k] = right[j].clone();
            j += 1;
        }
    }

    Ok(())
}