Merge pull request #4142 from iij/mergesort

replace quicksort with mergesort.

3 files changed, 58 insertions, 36 deletions

diff --git a/mrbgems/mruby-enum-ext/mrblib/enum.rb b/mrbgems/mruby-enum-ext/mrblib/enum.rb
index 6cbacdf9e..ba92decee 100644
--- a/mrbgems/mruby-enum-ext/mrblib/enum.rb
+++ b/mrbgems/mruby-enum-ext/mrblib/enum.rb
@@ -201,9 +201,7 @@ module Enumerable
       ary.push([block.call(e), i])
     }
     if ary.size > 1
-      ary.__sort_sub__(0, ary.size - 1) do |a,b|
-        a <=> b
-      end
+      ary.sort!
     end
     ary.collect{|e,i| orig[i]}
   end
diff --git a/mrblib/array.rb b/mrblib/array.rb
index 13c5d646c..ae0868410 100644
--- a/mrblib/array.rb
+++ b/mrblib/array.rb
@@ -193,43 +193,61 @@ class Array
   include Enumerable
 
   ##
-  # Quick sort
-  # left  : the beginning of sort region
-  # right : the end of sort region
-  def __sort_sub__(left, right, &block)
-    stack = [ [left, right] ]
+  # Sort all elements and replace +self+ with these
+  # elements.
+  def sort!(&block)
+    stack = [ [ 0, self.size - 1 ] ]
     until stack.empty?
-      left, right = stack.pop
-      if left < right
-        i = left
-        j = right
-        pivot = self[i + (j - i) / 2]
-        while true
-          while ((block)? block.call(self[i], pivot): (self[i] <=> pivot)) < 0
-            i += 1
-          end
-          while ((block)? block.call(pivot, self[j]): (pivot <=> self[j])) < 0
-            j -= 1
+      left, mid, right = stack.pop
+      if right == nil
+        right = mid
+        # sort self[left..right]
+        if left < right
+          if left + 1 == right
+            lval = self[left]
+            rval = self[right]
+            if (block&.call(lval, rval) || (lval <=> rval)) > 0
+              self[left]  = rval
+              self[right] = lval
+            end
+          else
+            mid = ((left + right + 1) / 2).floor
+            stack.push [ left, mid, right ]
+            stack.push [ mid, right ]
+            stack.push [ left, (mid - 1) ] if left < mid - 1
           end
-          break if (i >= j)
-          tmp = self[i]; self[i] = self[j]; self[j] = tmp;
-          i += 1
-          j -= 1
         end
-        stack.push [left, i-1]
-        stack.push [j+1, right]
-      end
-    end
-  end
-  #  private :__sort_sub__
+      else
+        lary = self[left, mid - left]
+        lsize = lary.size
 
-  ##
-  # Sort all elements and replace +self+ with these
-  # elements.
-  def sort!(&block)
-    size = self.size
-    if size > 1
-      __sort_sub__(0, size - 1, &block)
+        # The entity sharing between lary and self may cause a large memory
+        # copy operation in the merge loop below.  This harmless operation
+        # cancels the sharing and provides a huge performance gain.
+        lary[0] = lary[0]
+
+        # merge
+        lidx = 0
+        ridx = mid
+        (left..right).each { |i|
+          if lidx >= lsize
+            break
+          elsif ridx > right
+            self[i, lsize - lidx] = lary[lidx, lsize - lidx]
+            break
+          else
+            lval = lary[lidx]
+            rval = self[ridx]
+            if (block&.call(lval, rval) || (lval <=> rval)) <= 0
+              self[i] = lval
+              lidx += 1
+            else
+              self[i] = rval
+              ridx += 1
+            end
+          end
+        }
+      end
     end
     self
   end
diff --git a/test/t/array.rb b/test/t/array.rb
index ecec39363..53fbdcf1a 100644
--- a/test/t/array.rb
+++ b/test/t/array.rb
@@ -386,6 +386,12 @@ assert("Array#rindex") do
   assert_equal 0, $a.rindex(1)
 end
 
+assert('Array#sort!') do
+  a = [3, 2, 1]
+  assert_equal a, a.sort!      # sort! returns self.
+  assert_equal [1, 2, 3], a    # it is sorted.
+end
+
 assert('Array#freeze') do
   a = [].freeze
   assert_raise(RuntimeError) do