Ruby quick sort: stack level too deep (SystemStackError)

Question

def quick_sort(list)
  return list if list.size <= 1
  p = list.sample
  left, right = list.partition{|elmt| elmt <= p}
  quick_sort(left) + quick_sort(right)
end

a = [9,8,7,6,5,0,6]
b = quick_sort(a)
puts b

When I run it in the terminal, it shows:

quick_sort.rb:4: stack level too deep (SystemStackError)

However I could not see any problem on line 4. Any help would be appreciated!

Your `quick_sort` function never reaches a final state. It keeps calling itself until the system stack is exhausted. — lightswitch05, Jul 02 '14 at 20:39
@lightswitch05 Or it recurses too many times and reaches the stack depth limit. — Douglas F Shearer, Jul 02 '14 at 20:45

lightswitch05 · Answer 1 · 2014-07-02T20:59:02.720

You application isn't taking into account duplicate values. In your example, you have 6 twice. Once you break down the array into small enough chunks, you get a chuck like [6,6]. When you try to call partition on [6, 6], you get [[6, 6], []], which keeps trying to call quick_sort. Since it cannot be broken down and further then [6,6], it just keeps running until you fill up your system stack.

A simple solution would be to remove all duplicates before you check the size of the list. If the size is < 2 after you've removed your duplicates, then you have reached a final state.

Final Solution:

def quick_sort(list)
  return list if list.uniq.size < 2
  p = list.sample
  left, right = list.partition{|elmt| elmt <= p}
  quick_sort(left) + quick_sort(right)
end

a = [9,8,7,6,5,0,6]
b = quick_sort(a)

Of course, you could always just use Ruby's sorting function too:

[9,8,7,6,5,0,6].sort

Ruby quick sort: stack level too deep (SystemStackError)

1 Answers1