# Insertion Sort

**Publish date:**Jun 7, 2021

**Tags:**rust clrs algorithm

This implementation is pretty much straight out of the book and we’re required to use the `Copy`

trait as a result, limiting `T`

a great deal.

```
fn insertion_sort_with_copy<T: PartialOrd + Copy>(a: &mut [T]) {
for j in 1..a.len() {
let key = a[j];
let mut i = j;
while i > 0 && a[i - 1] > key {
a[i] = a[i - 1];
i -= 1;
}
a[i] = key;
}
}
```

By changing things around a little and using `swap`

, we can remove the need for the `Copy`

trait.

```
fn insertion_sort<T: PartialOrd>(a: &mut [T]) {
for j in 1..a.len() {
let mut i = j;
while i > 0 && a[i - 1] > a[i] {
a.swap(i - 1, i);
i -= 1;
}
}
}
```

The end!

*Thanks for reading! Please feel free to send me an email to talk more about this (or anything else for that matter).*