Reimplement sort method to reduce array copying.
MODIFY
mrbgems/mruby-enum-ext/mrblib/enum.rb
mrbgems/mruby-enum-ext/mrblib/enum.rb
@@ -201,7 +201,7 @@ module Enumerable
ary.push([block.call(e), i])
}
if ary.size > 1
- __sort_sub__(ary, ::Array.new(ary.size), 0, 0, ary.size - 1) do |a,b|
+ __sort_sub__(ary, 0, ary.size - 1) do |a,b|
a <=> b
end
end

MODIFY
mrblib/array.rb
mrblib/array.rb
+# 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

MODIFY
mrblib/enum.rb
mrblib/enum.rb
@@ -315,45 +315,6 @@ module Enumerable
# ISO 15.3.2.2.18
alias select find_all
- ##
- # TODO
- # Does this OK? Please test it.
- def __sort_sub__(sorted, work, src_ary, head, tail, &block)
- if head == tail
- sorted[head] = work[head] if src_ary == 1
- return
- end
-
- # on current step, which is a src ary?
- if src_ary == 0
- src, dst = sorted, work
- else
- src, dst = work, sorted
- end
-
- key = src[head] # key value for dividing values
- i, j = head, tail # position to store on the dst ary
-
- (head + 1).upto(tail){|idx|
- if ((block)? block.call(src[idx], key): (src[idx] <=> key)) > 0
- # larger than key
- dst[j] = src[idx]
- j -= 1
- else
- dst[i] = src[idx]
- i += 1
- end
- }
-
- sorted[i] = key
-
- # sort each sub-array
- src_ary = (src_ary + 1) % 2 # exchange a src ary
- __sort_sub__(sorted, work, src_ary, head, i - 1, &block) if i > head
- __sort_sub__(sorted, work, src_ary, i + 1, tail, &block) if i < tail
- end
-# private :__sort_sub__
-
##
# Return a sorted array of all elements
# which are yield by +each+. If no block
@@ -364,12 +325,7 @@ module Enumerable
#
# ISO 15.3.2.2.19
def sort(&block)
- ary = []
- self.each{|*val| ary.push(val.__svalue)}
- if ary.size > 1
- __sort_sub__(ary, ::Array.new(ary.size), 0, 0, ary.size - 1, &block)
- end
- ary
+ self.map{|*val| val.__svalue}.sort
end
##

Reimplement sort method to reduce array copying.