ABCL-1.0.0
(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.
ABCL's sort also seems a little slow. The psort benchmarks show too much speedup for only 2 cores (http://lparallel.com/download).
size 1000 | op < | SORT 11 size 1000 | op < | SORT 11 size 1000 | op < | SORT 12 size 1000 | op < | SORT 12 size 1000 | op < | PSORT 5 size 1000 | op < | PSORT 4 size 1000 | op < | PSORT 5 size 1000 | op < | PSORT 4
size 50000 | op < | SORT 1014 size 50000 | op < | SORT 1011 size 50000 | op < | SORT 1012 size 50000 | op < | SORT 1013 size 50000 | op < | PSORT 413 size 50000 | op < | PSORT 417 size 50000 | op < | PSORT 415 size 50000 | op < | PSORT 416
size 200000 | op < | SORT 4703 size 200000 | op < | SORT 4701 size 200000 | op < | SORT 4715 size 200000 | op < | SORT 4712 size 200000 | op < | PSORT 1977 size 200000 | op < | PSORT 1975 size 200000 | op < | PSORT 1979 size 200000 | op < | PSORT 1994
psort is based upon the following (posted to usenet by Roger Corman; free license).
(defun quicksort (vec lo hi comp-func) (if (> hi lo) (let* ((mid (round (+ lo hi) 2)) (i lo) (j (+ hi 1)) (p (elt vec mid))) (rotatef (elt vec mid) (elt vec lo)) ;; swap mid element to first (loop (loop do (incf i) until (or (> i hi) (funcall comp-func p (elt vec i)))) (loop do (decf j) until (or (<= j lo) (funcall comp-func (elt vec j) p))) (if (< j i) (return)) (rotatef (elt vec i)(elt vec j))) (rotatef (elt vec lo) (elt vec j)) ;;put partition element in place (quicksort vec lo (- j 1) comp-func) (quicksort vec i hi comp-func))) vec)
(defun qsort (sequence comp-func) (quicksort sequence 0 (- (length sequence) 1) comp-func))