From: "duerst (Martin Dürst)" Date: 2013-02-03T16:26:27+09:00 Subject: [ruby-core:51818] [ruby-trunk - Bug #7772] Consider bumping stack size in ruby_qsort Issue #7772 has been updated by duerst (Martin D��rst). It's very well known that Quicksort may create stack overflows. But it's also very well known how to deal with them: Check which of the remaining divisions is longer, and user recursion for the sorter part, and tail recursion simulated with a loop for the longer one. For a (conceptual, written using Ruby as executable pseudocode) example, please see quick_sort_recurse at http://www.sw.it.aoyama.ac.jp/2012/DA/programs/6qsort.rb. I haven't checked the C code, but I would be extremely surprised if this and other optimizations would not have been used in Ruby's sort implementation. ---------------------------------------- Bug #7772: Consider bumping stack size in ruby_qsort https://bugs.ruby-lang.org/issues/7772#change-35796 Author: Conrad.Irwin (Conrad Irwin) Status: Open Priority: Normal Assignee: Category: Target version: ruby -v: 1.9.3p362 At the moment the maximum size of the stack is 32. The comment implies this should be enough for arrays with up to 2**32 elements, but it's possible to create larger arrays on some big systems. I was not able to trigger a bug with: ([0, 1] * (2**32 + 10000)).sort! so it may actually never be a problem in practice, but it seems unsafe. -- http://bugs.ruby-lang.org/