Hello!

I am sorting strings by quick sort algorithm with two slightly different realizations.

First one where I use type vector of strings &[String] and second where I use vector of references to string [&String].

First type vector of strings works much faster. So, I have a question: why using references works so slow?

Below the code. To see huge difference in running time you can increase number of items from 10_000_000 to 100_000_000, for example. It depends on your hardware.

Frist one

```
fn main() {
let mut hash = std::collections::HashSet::new();
let now = std::time::Instant::now();
for i in 0..10_000_000 {
hash.insert(i.to_string());
}
println!("{:?} insert to hashmap", now.elapsed());
let now = std::time::Instant::now();
let mut v: Vec<String> = hash.iter().cloned().collect();
println!("{:?} collect keys to vector", now.elapsed());
let now = std::time::Instant::now();
quick_sort(&mut v);
println!("{:?} sorting vector", now.elapsed());
}
pub fn quick_sort(arr: &mut [String]) {
let len = arr.len();
_quick_sort(arr, 0, (len - 1) as isize);
}
fn _quick_sort(arr: &mut [String], low: isize, high: isize) {
if low < high {
let p = partition(arr, low, high);
_quick_sort(arr, low, p - 1);
_quick_sort(arr, p + 1, high);
}
}
fn partition(arr: &mut [String], low: isize, high: isize) -> isize {
let pivot = high as usize;
let mut store_index = low - 1;
let mut last_index = high;
loop {
store_index += 1;
while arr[store_index as usize] < arr[pivot] {
store_index += 1;
}
last_index -= 1;
while last_index >= 0 && arr[last_index as usize] > arr[pivot] {
last_index -= 1;
}
if store_index >= last_index {
break;
} else {
arr.swap(store_index as usize, last_index as usize);
}
}
arr.swap(store_index as usize, pivot);
store_index
}
```

and second one

```
fn main() {
let mut hash = std::collections::HashSet::new();
let now = std::time::Instant::now();
for i in 0..10_000_000 {
hash.insert(i.to_string());
}
println!("{:?} insert to hashmap", now.elapsed());
let now = std::time::Instant::now();
let mut v: Vec<&String> = hash.iter().collect();
println!("{:?} collect keys to vector", now.elapsed());
let now = std::time::Instant::now();
quick_sort(&mut v);
println!("{:?} sorting vector", now.elapsed());
}
pub fn quick_sort(arr: &mut [&String]) {
let len = arr.len();
_quick_sort(arr, 0, (len - 1) as isize);
}
fn _quick_sort(arr: &mut [&String], low: isize, high: isize) {
if low < high {
let p = partition(arr, low, high);
_quick_sort(arr, low, p - 1);
_quick_sort(arr, p + 1, high);
}
}
fn partition(arr: &mut [&String], low: isize, high: isize) -> isize {
let pivot = high as usize;
let mut store_index = low - 1;
let mut last_index = high;
loop {
store_index += 1;
while arr[store_index as usize] < arr[pivot] {
store_index += 1;
}
last_index -= 1;
while last_index >= 0 && arr[last_index as usize] > arr[pivot] {
last_index -= 1;
}
if store_index >= last_index {
break;
} else {
arr.swap(store_index as usize, last_index as usize);
}
}
arr.swap(store_index as usize, pivot);
store_index
}
```