Insertion sort algorithm gives overflow error

Question

When trying to run the insertion sort algorithm as shown below in Rust 1.15.

fn main() {
    println!("The sorted set is now: {:?}", insertion_sort(vec![5,2,4,6,1,3]));
}

fn insertion_sort(set: Vec<i32>) -> Vec<i32> {
    let mut A = set.to_vec();
    for j in 1..set.len() {
        let key = A[j];
        let mut i = j - 1;
        while (i >= 0) && (A[i] > key) {
            A[i + 1] = A[i];
            i = i - 1;
        }
        A[i + 1] = key;
    }
    A
}

I get the error:

thread 'main' panicked at 'attempt to subtract with overflow', insertion_sort.rs:12
note: Run with `RUST_BACKTRACE=1` for a backtrace

Why does an overflow happen here and how is the problem alleviated?

@SpencerWieczorek but the same exact code seems to run in python, with the same input — atomsmasher, Jun 17 '17 at 03:18
`i` has type `usize`, that is it is unsigned, thus condition `i >= 0` is always true. Besides, Rust doesn't have python's feature of allowing negative indexes. — red75prime, Jun 17 '17 at 04:58
Why don't you use [`slide::sort`](https://doc.rust-lang.org/std/primitive.slice.html#method.sort) ? — Stargateur, Jun 17 '17 at 10:33

score 2 · Accepted Answer · answered Jun 17 '17 at 04:57

The reason is you tried to calculate 0 - 1 in usize type, which is unsigned (nonnegative). This may lead to an error in Rust.

Why usize? Because Rust expects usize for lengths and indices. You can explicitly convert them into/from signed ones e.g. isize.

fn main() {
    println!("The sorted set is now: {:?}", insertion_sort(vec![5,2,4,6,1,3]));
}

fn insertion_sort(set: Vec<i32>) -> Vec<i32> {
    let mut A = set.to_vec();
    for j in 1..set.len() as isize {
        let key = A[j as usize];
        let mut i = j - 1;
        while (i >= 0) && (A[i as usize] > key) {
            A[(i + 1) as usize] = A[i as usize];
            i = i - 1;
        }
        A[(i + 1) as usize] = key;
    }
    A
}

Another solution, which I recommend, is to avoid negative indices at all. In this case you can use i + 1 instead of i like this:

fn main() {
    println!("The sorted set is now: {:?}", insertion_sort(vec![5,2,4,6,1,3]));
}

fn insertion_sort(set: Vec<i32>) -> Vec<i32> {
    let mut A = set.to_vec();
    for j in 1..set.len() {
        let key = A[j];
        let mut i = j;
        while (i > 0) && (A[i - 1] > key) {
            A[i] = A[i - 1];
            i = i - 1;
        }
        A[i] = key;
    }
    A
}

Insertion sort algorithm gives overflow error

1 Answers1