replace quicksort with mergesort.
MODIFY
mrbgems/mruby-enum-ext/mrblib/enum.rb
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

MODIFY
mrblib/array.rb
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
+ left, mid, right = stack.pop
+ if right == nil
+ right = mid
+ # sort self[left..right]
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
+ 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
- while ((block)? block.call(pivot, self[j]): (pivot <=> self[j])) < 0
- j -= 1
+ 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]
+ else
+ lary = self[left, mid - left]
+ lsize = lary.size
+
+ # 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
- # private :__sort_sub__
-
- ##
- # Sort all elements and replace +self+ with these
- # elements.
- def sort!(&block)
- size = self.size
- if size > 1
- __sort_sub__(0, size - 1, &block)
end
self
end

MODIFY
test/t/array.rb
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

replace quicksort with mergesort.