Cannot move out of here move occurs because `slice[_]` has type `T`, which does not implement the `Copy` trait

Question

I am trying to write quick sort in Rust, I got it working when I used the specific type [i32] but I get an error when I try to use [T].

fn main() {
    let mut arr = vec![4,3,2,1];
    quick_sort(&mut arr);
    println!("{:?}", arr);
}

fn partition<T: Ord>(slice: &mut [T]) -> usize {
    let end = slice.len() - 1;
    let pivot = slice[end];
    let mut j = 0;
    for i in 0..end {
        if slice[j] <= pivot {
            slice.swap(i, j);
            j += 1;
        }
    }
    slice.swap(end, j);
    j
}

fn quick_sort<T: Ord>(slice: &mut [T]) {
    if !slice.is_empty() {
        let j = partition(slice);
        let len = slice.len();
        
        quick_sort(&mut slice[0..j]);
        quick_sort(&mut slice[j+1..len]);
    }
}

I get the following error:

error[E0508]: cannot move out of type `[T]`, a non-copy slice
  --> src/main.rs:9:17
   |
  9|     let pivot = slice[end];
   |                 ^^^^^^^^^^ cannot move out of here
   |                            move occurs because `slice[_]` has type `T`, 
   |                            which does not implement the `Copy` trait
   |                            help: consider borrowing here: `&slice[end]`

When let pivot = &slice[end]; , I get a different error:

error[E0308]: mismatched types
  --> src/main.rs:12:22
   |
  7| fn partition<T: Ord>(slice: &mut [T]) -> usize {
   |              - this type parameter
...
 12|        if slice[j] <= pivot {
   |                       ^^^^^ expected type parameter `T`, found `&T`
   = note: expected type parameter `T`
                   found reference `&T`

I cannot get this to work with [T].

Answer 1

We can fix the "expected type parameter T, found &T" error by changing the if to:

if &slice[j] <= pivot {

but that runs into another error:

error[E0502]: cannot borrow `*slice` as mutable because it is also borrowed as immutable
  --> src/main.rs:13:13
   |
9  |     let pivot = &slice[end];
   |                 ----------- immutable borrow occurs here
...
12 |         if &slice[j] <= pivot {
   |                         ----- immutable borrow later used here
13 |             slice.swap(i, j);
   |             ^^^^^^^^^^^^^^^^ mutable borrow occurs here

This is because we are taking a reference to a value from the slice and while that reference is alive, we are calling a method that requires mutable access to the slice.

To fix this, we can inline the referencing into the if statement itself:

fn partition<T: Ord>(slice: &mut [T]) -> usize {
    let end = slice.len() - 1;
    let mut j = 0;
    for i in 0..end {
        if slice[j] <= slice[end] {
            slice.swap(i, j);
            j += 1;
        }
    }
    slice.swap(end, j);
    j
}

Output:

[1, 2, 3, 4]

Playground

---

The reason this worked for [i32] is because calling slice[end] implicitly created a copy of the value because i32 implements the Copy trait. If a type does not implement Copy, you need to either take a reference using &slice[index] or if it implements Clone, call slice[index].clone(). In this code you have a generic T which does not implement either of those.