[armedbear-devel] Patch with improvements to stable-sort and sort

[Mark Evenson]

On 2/11/12 11:04 AM, Jorge Tavares wrote:

> I send in attach a patch with further improvements to sort and
stable-sort for sequences other than lists. In short, the patch includes
a merge sort for vectors. To allow different types I've written the
algorithm using macros and these generate the appropriate code according
to the vector type. This way the algorithm is in a single place avoiding
duplication of code. The macros also take care of the situation of when
no key is present, avoiding the use of unnecessary funcalls. The
quicksort algorithm was also refactored in the same way.
>
> I've tested the algorithms and they seem to be working correctly

[…]

As noted earlier, while Jorge's patches mostly seemed to work, they 
cause failures in the ANSI tests which invoked CL:STABLE-SORT on a 
BIT-VECTOR or a STRING.  After a bit of delving into the macrology to 
obtain a minimum understanding of what was going on, I was able to to 
kludge together [r13931][1] which now relaxes the type used for 
sequences as VECTOR rather than SIMPLE-VECTOR.  Although I suspect that 
such a distinction is not really used at the present time by our 
compiler, it is a bit of a shame to lose information that could 
potentially be useful in the future, but I don't think I will make 
further useful progress on this issue at the present time so I have 
closed [ticket #196][2].

[1]: http://trac.common-lisp.net/armedbear/changeset/13931
[2]: http://trac.common-lisp.net/armedbear/ticket/196

Those whose macro-fu is better than mine are invited to submit a less 
kludgey fix.