When passing a mutable array reference into a function that also takes a mutable array reference, why is &mut not stated?

Question

I am trying to implement the quick sort algorithm for an array of i32. My question is about an apparent inconsistency in the use of &mut when passing in arrays to functions. My code:

fn main() {
    let mut my_array = [5, 2, 8, 7];
    let high = my_array.len() - 1;
    quick_sort(&mut my_array, 0, high);
    print!("{:?}", my_array);
}

fn quick_sort(array: &mut [i32], low: usize, high: usize) {
    let pivot_idx = partition(array, low, high);

    // Separately sort elements before partition and after partition
    if pivot_idx > low {
        quick_sort(array, low, pivot_idx - 1);
    }
    if pivot_idx < high {
        quick_sort(array, pivot_idx + 1, high);
    }
}

fn partition(array: &mut [i32], low: usize, high: usize) -> usize {
    let pivot = array[high]; // pivot
    let mut i = low;

    for j in low..high {
        // If current element is less than or equal to pivot
        if array[j] <= pivot {
            let swapper_variable = array[i];
            array[i] = array[j];
            array[j] = swapper_variable;
            i += 1; // increment index of smaller element
        }
    }

    let swapper_variable = array[i];
    array[i] = array[high];
    array[high] = swapper_variable;
    return i;
}

My code works, but should it? In main I call quick_sort with quick_sort(&mut my_array, 0, high), but the recursive call within quick_sort is quick_sort(array, low, pivot_idx - 1), without the &mut.

Furthermore, also within quick_sort, I call partition with partition(array, low, high), but partition takes a mutable array as an argument and I haven't specified &mut in the call! If I do try to put &mut in the partition function call, the code will not compile: error[E0596]: cannot borrow `array` as mutable, as it is not declared as mutable --> src/main.rs:9:31 | 8 | fn quick_sort(array: &mut [i32], low: usize, high: usize) { | ----- help: consider changing this to be mutable: `mut array` 9 | let pivot_idx = partition(&mut array, low, high); | ^^^^^^^^^^ cannot borrow as mutable

So it seems there's some confusion as to what's mutable, the array itself or the pointer(?) to the array. But it seems to me that I should be able to call functions within quick_sort in the same manner that I called quick_sort originally from main. As far as I know, the point of forcing &mut to be explicitly placed in the function call is that doing so makes it easy to see that the called function might modify the argument, but the calls within quick_sort give no indication that they modify the array.

Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=62813cd1bd23d8b1a36d6126d4305800

Psidom Psidom · Accepted Answer · 2019-12-24T22:40:21

In your main function, my_array is of type [i32], but quick_sort requires &mut [i32], which is why you need &mut my_array; In your quick_sort function, however parameter array is already of type &mut [i32], which is why you can directly pass it to partition and recursive quick_sort call. This is exactly how you should call your functions following the type annotations.

fn main() {
    let mut my_array = [5, 2, 8, 7];         // [i32]
    quick_sort(&mut my_array, 0, high);      // &mut my_array gives type &mut [i32]
}

fn quick_sort(array: &mut [i32], low: usize, high: usize) {
    let pivot_idx = partition(array, low, high);    
    // notice array is already of type &mut [i32], which is required by partition function,
    // you shouldn't take another reference on top of it
    ...
}

When passing a mutable array reference into a function that also takes a mutable array reference, why is &mut not stated?

1 Answers