auto merge of #11064 : huonw/rust/vec-sort, r=alexcrichton

This uses quite a bit of unsafe code for speed and failure safety, and allocates `2*n` temporary storage.

[Performance](https://gist.github.com/huonw/5547f2478380288a28c2):

|      n |      new | priority_queue |   quick3 |
|-------:|---------:|---------------:|---------:|
|      5 |      200 |            155 |      106 |
|    100 |     6490 |           8750 |     5810 |
|  10000 |  1300000 |        1790000 |  1060000 |
| 100000 | 16700000 |       23600000 | 12700000 |
| sorted |   520000 |        1380000 | 53900000 |
|  trend |  1310000 |        1690000 |  1100000 |

(The times are in nanoseconds, having subtracted the set-up time (i.e. the `just_generate` bench target).)

I imagine that there is still significant room for improvement, particularly because both priority_queue and quick3 are doing a static call via `Ord` or `TotalOrd` for the comparisons, while this is using a (boxed) closure.

Also, this code does not `clone`, unlike `quick_sort3`; and is stable, unlike both of the others.

0 files changed, 0 insertions, 0 deletions