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.

1 files changed, 1 insertions, 3 deletions

diff --git a/src/libsyntax/attr.rs b/src/libsyntax/attr.rs
index 5e16213190c..8dff321ca0e 100644
--- a/src/libsyntax/attr.rs
+++ b/src/libsyntax/attr.rs
@@ -10,8 +10,6 @@
 
 // Functions dealing with attributes and meta items
 
-use extra;
-
 use ast;
 use ast::{Attribute, Attribute_, MetaItem, MetaWord, MetaNameValue, MetaList};
 use codemap::{Span, Spanned, spanned, dummy_spanned};
@@ -205,7 +203,7 @@ pub fn sort_meta_items(items: &[@MetaItem]) -> ~[@MetaItem] {
         .map(|&mi| (mi.name(), mi))
         .collect::<~[(@str, @MetaItem)]>();
 
-    extra::sort::quick_sort(v, |&(a, _), &(b, _)| a <= b);
+    v.sort_by(|&(a, _), &(b, _)| a.cmp(&b));
 
     // There doesn't seem to be a more optimal way to do this
     v.move_iter().map(|(_, m)| {