merge_sort.rs ported from C

merge_sort.rs

fn main() {
     let mut list = vec![9_u64, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0];
     println!("Test - Before sort: {}", list);
     merge_sort(0, list.len() as u64, &mut list);
     println!("Test - After sort: {}", list);
     
     // Test - Before sort: [9, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0]
     // Test - After sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
}
 
pub fn merge_sort(left: u64, right: u64, list: &mut Vec<u64>) {
    // println!("mergesort left:{} right:{} list:{}", left, right, list);
    
    // base case
    if right - left <= 1 {
        return;
    }
    
    // get slice indicies
    let l_start = left;
    let l_end = (left+right)/2;
    let r_start = l_end;
    let r_end = right;
    
    // recursive call on left half
    merge_sort(l_start, l_end, list);
    
    // recursive call or right half
    merge_sort(r_start, r_end, list);
    
    // merge sorted right and left halves back together
    merge(list, l_start, l_end, r_start, r_end);
}
 
fn merge(list: &mut Vec<u64>, l_start: u64, l_end: u64, r_start: u64, r_end: u64) {
    // println!("merge l_start:{} l_end:{} r_start:{} r_end:{} list:{}", l_start, l_end, r_start, r_end, list);
    
    // temporary list sizes
    let l_len = l_end - l_start;
    let r_len = r_end - r_start;
    
    // temporary lists for comparison
    let mut l_half: Vec<u64> = Vec::with_capacity(l_len as uint);
    let mut r_half: Vec<u64> = Vec::with_capacity(r_len as uint);
    
    let mut l: u64 = 0;
    let mut r: u64 = 0;
    
    // copy values into temporary lists
    
    let mut i = l_start;
    while i < l_end {
        l_half.insert(l as uint, list[i as uint]);
        i += 1;
        l += 1;
    }
    
    i = r_start;
    while i < r_end {
        r_half.insert(r as uint, list[i as uint]);
        i += 1;
        r += 1;
    }
    
    
    // merge the values back into positions in main list 
    i = l_start;
    r = 0;
    l = 0;
    while l < l_len && r < r_len {
        // if left value < r value, move left value
        if l_half[l as uint] < r_half[r as uint] {
            list[i as uint] = l_half[l as uint];
            l += 1;
        }
        // else move right value
        else {
            list[i as uint] = r_half[r as uint];
            r += 1;
        }
        
        i += 1;
    }
    
    // handle leftover values
    while l < l_len {
        list[i as uint] = l_half[l as uint];
        i += 1;
        l += 1;
    }
    
    while r < r_len {
        list[i as uint] = r_half[r as uint];
        i += 1;
        r += 1;
    }
}