From ea6a1bdf6ba754f3b96e3a46f9173b17ff18ed07 Mon Sep 17 00:00:00 2001
From: varkor <github@varkor.com>
Date: Thu, 1 Mar 2018 10:46:06 +0000
Subject: Compute each key only one during slice::sort_by_key

---
 src/liballoc/slice.rs | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

(limited to 'src/liballoc/slice.rs')

diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs
index dc40062ef13..c57f1e7f572 100644
--- a/src/liballoc/slice.rs
+++ b/src/liballoc/slice.rs
@@ -1328,10 +1328,18 @@ impl<T> [T] {
     /// ```
     #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
     #[inline]
-    pub fn sort_by_key<B, F>(&mut self, mut f: F)
+    pub fn sort_by_key<B, F>(&mut self, f: F)
         where F: FnMut(&T) -> B, B: Ord
     {
-        merge_sort(self, |a, b| f(a).lt(&f(b)));
+        let mut indices: Vec<_> = self.iter().map(f).enumerate().map(|(i, k)| (k, i)).collect();
+        indices.sort();
+        for i in 0..self.len() {
+            let mut index = indices[i].1;
+            while index < i {
+                index = indices[index].1;
+            }
+            self.swap(i, index);
+        }
     }
 
     /// Sorts the slice, but may not preserve the order of equal elements.
-- 
cgit 1.4.1-3-g733a5