2007/12/3, Charles Oliver Nutter <charles.nutter / sun.com>:

> JRuby's Array implementation is largely a port of MRI's, so I'm sure we
> just have the same quadratic implementation. Voroztsov, do you have an
> explanation for why the current implementation is quadratic?

I don't now. Only two assumptions

1)
Each iteration we do the following:

    if (rb_ary_includes(memo, id)) {
	rb_raise(rb_eArgError, "tried to flatten recursive array");
    }

 So we need to check if array was already met (to avoid self-included arrays).
 It's worth to switch memo class to Hash.

2)
Each iteration we do the following:

   rb_ary_splice(ary, idx, 1, ary2);

  It also can cause quadratic time.


> Other than
> the ordering issue Ryan pointed out, is there any functional difference?
>

Yes
1) my version does not support argument
2) self-included array kills it

But both can be solved in non-quadratic time.
We can get rid of the second difference in O(L log L).

I posted fixed version which works correct with Ryan's sample

> - Charlie
>
>