From 7b8d784040f1fd88fce2658b704b300f7421c885 Mon Sep 17 00:00:00 2001
From: "Yukihiro \"Matz\" Matsumoto" <matz@ruby-lang.org>
Date: Tue, 25 Jul 2017 14:42:38 +0900
Subject: Reimplement sort method to reduce array copying.

---
 mrblib/array.rb | 39 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 38 insertions(+), 1 deletion(-)

(limited to 'mrblib/array.rb')

diff --git a/mrblib/array.rb b/mrblib/array.rb
index d5a2d8405..be98f217e 100644
--- a/mrblib/array.rb
+++ b/mrblib/array.rb
@@ -1,3 +1,4 @@
+# coding: utf-8
 ##
 # Array
 #
@@ -192,10 +193,46 @@ class Array
   # ISO 15.2.12.3
   include Enumerable
 
+  ##
+  # Quick sort
+  # a     : the array to sort
+  # left  : the beginning of sort region
+  # right : the end of sort region
+  def __sort_sub__(a, left, right, &block)
+    if left < right
+      i = left
+      j = right
+      pivot = a[i + (j - i) / 2]
+      while true
+        while ((block)? block.call(a[i], pivot): (a[i] <=> pivot)) < 0
+          i += 1
+        end
+        while ((block)? block.call(pivot, a[j]): (pivot <=> a[j])) < 0
+          j -= 1
+        end
+        break if (i >= j)
+        tmp = a[i]; a[i] = a[j]; a[j] = tmp;
+        i += 1
+        j -= 1
+      end
+      __sort_sub__(a, left, i-1, &block)
+      __sort_sub__(a, j+1, right, &block)
+    end
+  end
+  #  private :__sort_sub__
+
   ##
   # Sort all elements and replace +self+ with these
   # elements.
   def sort!(&block)
-    self.replace(self.sort(&block))
+    size = self.size
+    if size > 1
+      __sort_sub__(self, 0, size - 1, &block)
+    end
+    self
+  end
+
+  def sort(&block)
+    self.dup.sort!(&block)
   end
 end
-- 
cgit v1.2.3