Hi,
I'm sending a patch that solves the issue reported in ticket #187. The quicksort function picks the pivot by selecting a midpoint and also sorts the smaller partition first. These are enough to avoid the stack overflow problem as reported. I've performed some tests and it looks it is correct.
Below I include a sample session, including the test case in the ticket:
idesk:abcl jast$ ./abcl Armed Bear Common Lisp 1.1.0-dev-svn-13848M Java 1.6.0_29 Apple Inc. Java HotSpot(TM) 64-Bit Server VM Low-level initialization completed in 0.307 seconds. Startup completed in 0.945 seconds. Loading /Users/jast/.abclrc completed in 4.528 seconds. Type ":help" for a list of available commands. CL-USER(1): (ql:quickload "alexandria") To load "alexandria": Load 1 ASDF system: alexandria ; Loading "alexandria" ("alexandria") CL-USER(2): (defparameter *sorted* (make-array 1000000 :initial-contents (alexandria:iota 1000000))) *SORTED* CL-USER(3): (defparameter *numbers* (alexandria:shuffle (copy-seq *sorted*))) *NUMBERS* CL-USER(4): (equalp *sorted* *numbers*) NIL CL-USER(5): (time (progn (setf *numbers* (sort *numbers* #'<)) nil)) 2.157 seconds real time 3 cons cells NIL CL-USER(6): (equalp *sorted* *numbers*) T CL-USER(7): (let ((a (map-into (make-array 10000) (let ((x 0)) (lambda () (incf x)))))) (sort a #'<) nil) NIL CL-USER(8): (time (progn (setf *numbers* (sort *numbers* #'<)) nil)) 1.074 seconds real time 3 cons cells NIL CL-USER(9):
With these changes, sort seems to be a little faster (for vectors) although I was not worried with optimizations. In ABCL 1.0.1, in my machine, sorting 1000000 random integers takes around 10s on average while now it takes 2s. However, I must point out I didn't do any serious and proper benchmarking, just some runs.
I will be happy to answer any questions if necessary.
Cheers, Jorge Tavares