New inline stable sort for vectors
This PR should improve on the current stable sorting of vectors, fixing issues such as #217 (closed) (bug) and #101 (closed) (performance).
Full disclosure: The merge sort algorithm was completely stolen from sbcl.
I'm sure the new version can be optimized, for example by inlining stable-sort-merge-vectors
, and by treating simple-arrays differently.
But for now, it already has slightly better performance on the sequences that I tested with, for example running:
(time (dotimes (x 50000)
(defparameter *my-arr*
(make-array 9 :initial-contents
(list
(cons 3 'a)
(cons 2 'b)
(cons 2 'c)
(cons 2 'd)
(cons 3 'e)
(cons 2 'f)
(cons 2 'g)
(cons 2 'h)
(cons 1 'i))))
(stable-sort *my-arr* #'< :key #'car)))
gave me 0.34 sec in the old version, and 0.28sec in the new one (even with the overhead of the make-array call, which is the same for both). But most importantly, the new version leaves the array sorted, which fixes bug #217 (closed):
> *my-arr*
#A(T (9) ((1 . I) (2 . B) (2 . C) (2 . D) (2 . F) (2 . G) (2 . H) (3 . A) (3 . E)))
while in the old-version:
> *my-arr*
#A(T (9) ((3 . A) (2 . B) (2 . C) (2 . D) (3 . E) (2 . F) (2 . G) (2 . H) (1 . I)))
The example in #217 (closed) also works now, of course:
> (let ((a (copy-seq "BCA")))
(stable-sort a #'char<)
a)
"ABC"