insertion_sort.rs

fn swap(arr: &mut Vec<int>, i: uint, j: uint) -> &Vec<int> {
    let buf = arr[i];
    arr[i] = arr[j];
    arr[j] = buf;
    arr
}

fn insertion_sort(arr: &mut Vec<int>) -> &Vec<int> {
    for i in range(1, arr.len()) {
        let key = arr[i];
        let mut j = i - 1;
        while j > 0 && arr[j] > key {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
        if arr[0] > arr[1] {
            swap(arr, 0, 1);
        }
    }
    arr
}