Hi,

alex zz wrote in post #1066577:

But it shows stack level too deep error.

I tried to add puts after

left,right=parti(items,0,items.length)

and see iterate outputs.

Any thoughts?

The parti method fails for two element arrays, which are already

ordered. In this case the method will just return the original array and

force quicksort into an endless loop.

As an example:

You have parti([1, 2], 0, 1)

i will start with 1. Since the second element is not smaller than the

first one, the each iterator will do nothing. The same goes for the

swapping. But when you create the two subarrays, you will run into

trouble: i - 2 is -1, so the left subarray will be from the first

element to the last (negative indices count from right to left,

beginning with -1). This results in the original array [1, 2].

The solution would be to simply leave out the swapping (which seems

senseless to me, anyway) und take s[1 … i - 1] as the left subarray.

By the way, in the quicksort method it should say

left, right= parti(items, 0,items.length - 1)

rather than

left, right= parti(items, 0, items.length)

But I guess you already corrected that, because otherwise the method

wouldn’t have worked at all.

Actually you don’t even need the indices. It seems you mixed up two

different quicksort approaches: operating on the original array (called

“in-place”) and creating subarrays like you do. You only need the

indices if you do in-place sorting.