Stack Overflow for Worst-case Vector Sort

[Mark Evenson]

​James Lawrence reports on armedbear-devel that ABCL-1.0.0 overflows its stack when sorting an array of 10^4 elements:

   (let ((a (map-into (make-array 10000)
                      (let ((x 0))
                        (lambda () (incf x))))))
     (sort a #'<)
     nil)
=>
Stack overflow.
  [Condition of type STORAGE-CONDITION]

 0: (#<FUNCTION {7F535BDF}> #<STORAGE-CONDITION {74A2B3B8}>
#<FUNCTION {7F535BDF}>)
 1: (APPLY #<FUNCTION {7F535BDF}> (#<STORAGE-CONDITION {74A2B3B8}>
#<FUNCTION {7F535BDF}>))
 2: (SYSTEM::RUN-HOOK SYSTEM::*INVOKE-DEBUGGER-HOOK*
#<STORAGE-CONDITION {74A2B3B8}> #<FUNCTION {7F535BDF}>)
 3: (INVOKE-DEBUGGER #<STORAGE-CONDITION {74A2B3B8}>)
 4: org.armedbear.lisp.Lisp.error(Lisp.java:374)
 5: org.armedbear.lisp.Java$pf_jrun_exception_protected.execute(Java.java:1315)
 6: org.armedbear.lisp.Symbol.execute(Symbol.java:785)
 7: org.armedbear.lisp.LispThread.execute(LispThread.java:649)
 8: org.armedbear.lisp.swank_469.execute(swank.lisp:2116)
 9: org.armedbear.lisp.LispThread.execute(LispThread.java:683)
10: org.armedbear.lisp.Primitives$pf_apply.execute(Primitives.java:2797)
11: (JAVA:JRUN-EXCEPTION-PROTECTED #<FUNCTION {39B4CEC7}>)

It looks like the quick-sort function (attributed to ECL) pivots off
the first element. I would suggest using a midpoint instead.

[Mark Evenson]

A new implementation that addresses this problem was provided by Jorge Tavares in r13852.

[Mark Evenson]

See #196 .