rust-lang/rust — pull request #16557 by Gankro (2014-08-17 16:07:14+00:00)
Title: Add resort to slice/vec

We have a perfectly good implementation of insertion sort available, but don't expose it publicly. It's a *great* sorting algorithm if the data in known to be mostly sorted (e.g. it was already sorted, and we've only touched a few elements).

I think the benchmarks speak for themselves. On sorted data it completely *destroys* `sort` (because it just reads the damn thing and calls it a day). Benchmark results are from `make check-collections PLEASE_BENCH=1 NO_REBUILD=1`, Can rebuild with different flags if desired:

```
test slice::bench::resort_big_sorted ... bench: 54309 ns/iter (+/- 4181) = 5892 MB/s
test slice::bench::resort_sorted ... bench: 43509 ns/iter (+/- 376) = 1838 MB/s

test slice::bench::sort_big_sorted ... bench: 1721006 ns/iter (+/- 366156) = 185 MB/s
test slice::bench::sort_random_large ... bench: 2506750 ns/iter (+/- 115227) = 31 MB/s
```

Other ops:
```
test slice::bench::resort_big_random_large ... bench: 115285904 ns/iter (+/- 2612076) = 2 MB/s
test slice::bench::resort_big_random_medium ... bench: 15938 ns/iter (+/- 478) = 200 MB/s
test slice::bench::resort_big_random_small ... bench: 445 ns/iter (+/- 20) = 359 MB/s
test slice::bench::resort_random_large ... bench: 44449508 ns/iter (+/- 747584) = 1 MB/s
test slice::bench::resort_random_medium ... bench: 9628 ns/iter (+/- 119) = 83 MB/s
test slice::bench::resort_random_small ... bench: 285 ns/iter (+/- 5) = 140 MB/s

test slice::bench::sort_big_random_large ... bench: 4066801 ns/iter (+/- 535054) = 78 MB/s
test slice::bench::sort_big_random_medium ... bench: 15441 ns/iter (+/- 549) = 207 MB/s
test slice::bench::sort_big_random_small ... bench: 484 ns/iter (+/- 7) = 330 MB/s
test slice::bench::sort_random_medium ... bench: 13135 ns/iter (+/- 574) = 60 MB/s
test slice::bench::sort_random_small ... bench: 346 ns/iter (+/- 15) = 115 MB/s
test slice::bench::sort_sorted ... bench: 726430 ns/iter (+/- 52568) = 110 MB/s
```

I didn't write any new benches to test e.g. "a couple elements are out of order". I can if it's desired. I also didn't add any unit tests since `resort` is implicitly tested by `sort`, for the most part.