[armedbear-ticket] [armedbear] #196: STABLE-SORT is only stable for lists

[armedbear]

#196: STABLE-SORT is only stable for lists
------------------------------+---------------------------------------------
 Reporter:  mevenson          |       Owner:  ehuelsmann
     Type:  defect            |      Status:  new       
 Priority:  major             |   Milestone:  1.1.0     
Component:  interpreter       |     Version:  1.0.1     
 Keywords:  ansi-conformance  |  
------------------------------+---------------------------------------------
 [http://article.gmane.org/gmane.lisp.armedbear.devel/2204 Jorge Tavares
 reports on armedbear-devel@]:

 {{{
 Recently I started to investigate the different CL sort implementations
 and found that stable-sort in ABCL does not execute as required. The
 problem is that stable-sort is only stable for lists and not for all type
 of sequences (i.e., elements considered equal by the predicate should stay
 in their original order).

 A very simple test shows this error:

 idesk:~ jast$ abcl
 Armed Bear Common Lisp 1.0.1
 Java 1.6.0_29 Apple Inc.
 Java HotSpot(TM) 64-Bit Server VM
 Low-level initialization completed in 0.399 seconds.
 Startup completed in 1.069 seconds.
 Loading /Users/jast/.abclrc completed in 4.8 seconds.
 Type ":help" for a list of available commands.
 CL-USER(1): (defparameter *stuff* #((1 0.31648433) (0 0.2704757) (0
 0.48931926) (1 0.9958766) (0 0.49251676)))
 *STUFF*
 CL-USER(2): (setf *stuff* (stable-sort *stuff* #'< :key #'first))
 #((0 0.49251676) (0 0.2704757) (0 0.48931926) (1 0.31648433) (1
 0.9958766))

 The above test is short and simple to understand: *stuff* contains an
 array where each element is a pair. The first element of a pair is the key
 and the second the data. With this in mind, the expected result should
 have been: #((0 0.2704757) (0 0.48931926) (0 0.49251676) (1 0.31648433) (1
 0.9958766)).

 The same error happens with larger arrays and other types of data. I also
 tested it in SBCL, CCL, ECL and CLisp and for these implementations the
 results are the expected. Only ABCL differs form the major open source
 implementations (I didn't test in ACL or LW).

 The reason for this bug is actually quite simple. In sort.lisp, in the
 definition of stable-sort, seq-dispatch calls for the non-list sequences
 the quicksort algorithm, which is not stable. For lists it calls merge
 sort (which is stable) and the problem does not arise.

 As a quick fix, I send in attach a patch that uses in stable-sort merge
 sort for all sequences. This is done by coercing the sequence to list,
 calling merge sort and coercing it back to the original sequence type.
 However, as a long term improvement, the best solution would be to
 implement a merge sort for non-list sequences.
 }}}

-- 
Ticket URL: <http://trac.common-lisp.net/armedbear/ticket/196>
armedbear <http://common-lisp.net/project/armedbear>
armedbear