sort method should not consume system stack.
@@ -197,6 +197,9 @@ class Array
# left : the beginning of sort region
# right : the end of sort region
def __sort_sub__(left, right, &block)
+ stack = [ [left, right] ]
+ until stack.empty?
+ left, right = stack.pop
if left < right
i = left
j = right
@@ -213,8 +216,9 @@ class Array
i += 1
j -= 1
end
- __sort_sub__(left, i-1, &block)
- __sort_sub__(j+1, right, &block)
+ stack.push [left, i-1]
+ stack.push [j+1, right]
+ end
end
end
# private :__sort_sub__
