[armedbear-devel] bug report: stable-sort is only stable for lists

[Jorge Tavares]

Dear ABCL developers, 

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.


Cheers,
Jorge Tavares

-- 
http://jorgetavares.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: stable-sort-fix.diff
Type: application/octet-stream
Size: 628 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/armedbear-devel/attachments/20120131/361027ef/attachment.obj>