Rust sorting algorithms (selection, bubble, quick, shell, merge)

I have written some sorting algorithms in Rust and wanted to see how terrible they were.

What I am looking for:

• Bugs

• Performance improvements

• Idiomatic code

• Maybe even a functional approach to the sorting algos

• Why is the merge sort so slow? Is it my implementation?

Note you will need rand = '*' in your Cargo.toml for running tests/benches. All tests pass at this point and here are the benches from my machine.

test tests::bench_large_bubble_sort    ... bench:   1,294,490 ns/iter (+/- 188,917)
test tests::bench_large_merge_sort     ... bench:   1,196,096 ns/iter (+/- 141,654)
test tests::bench_large_quick_sort     ... bench:      70,173 ns/iter (+/- 11,150)
test tests::bench_large_selection_sort ... bench:   1,351,724 ns/iter (+/- 197,069)
test tests::bench_large_shell_sort     ... bench:      95,080 ns/iter (+/- 14,972)
test tests::bench_small_bubble_sort    ... bench:         923 ns/iter (+/- 118)
test tests::bench_small_merge_sort     ... bench:       4,479 ns/iter (+/- 743)
test tests::bench_small_quick_sort     ... bench:         824 ns/iter (+/- 103)
test tests::bench_small_selection_sort ... bench:         788 ns/iter (+/- 129)
test tests::bench_small_shell_sort     ... bench:         852 ns/iter (+/- 117)

```
#![feature(test)]
#![feature(step_by)]

fn selection_sort(mut values: Vec) -> Vec {
let mut min;
for outer in 0..values.len() {
min = outer;
for inner in (outer + 1)..values.len() {
if values[inner] ) -> Vec {
let mut swapped = true;
let mut j = 0;
while swapped {
swapped = false;
j += 1;
for inner in 0..(values.len() - j) {
if values[inner] > values[inner + 1] {
let tmp = values[inner];
values[inner] = values[inner + 1];
values[inner + 1] = tmp;
swapped = true;
}
}
}
return values;
}

fn quick_sort(mut values: &mut Vec, start: Option, end: Option) {

The merge function in your merge sort is \$\mathcal{O}(n^2)\$ (it's meant to be \$\mathcal{O}(n)\$) because

v.extend(merge(left[1..].to_vec(), right));

uses extend, which takes \$\mathcal{O}(n)\$ time, and you do it \$\mathcal{O}(n)\$ times, which makes \$\mathcal{O}(n^2)\$ total.

The merge is normally implemented by pushing one element at a time to a mutable buffer.

StackExchange Code Review Q#141605, answer score: 4