Don't use Franz sortcar!

[Rod Brooks <ROD@SU-AI.ARPA>]

Somewhat bizzarely it seems that Franz Lisp sort and sortcar have
different time complexities. sort is good and sortcar is bad so
I suggest you convert your sortcar's to sort's until someone sorts
this out. The code and transcript below use both sort and sortcar
to sort a list of length n (the list happens to start in precisely
reverse order). A count of the number of calls to the comparison
function is kept. The results show that sort takes n*log(n)
comparisons while sortcar takes n*n. The problem should
be fixable by throwing out code as there must be two sorters lurking
in there!

;;;;;;;;;;;;;;;

(defun gen (n)
    (do ((i 0 (1+ i))
	 (l () (cons (cons i ()) l)))
	((= i n)
	 l)))

(defun compare (x y)
    (setq *count* (1+ *count*))
    (< x y))

(defun compare-cars (x y) (compare (car x) (car y)))

(defun count-sort (n)
    (let ((*count* 0))
	 (sort (gen n) #'compare-cars)
	 *count*))

(defun count-sortcar (n)
    (let ((*count* 0))
	 (sortcar (gen n) #'compare)
	 *count*))

(defun test (n)
    (let ((csort (count-sort n))
	  (csortcar (count-sortcar n)))
	 (list n
	       csort
	       csortcar
	       (/$ (float csort) (*$ (float n) (log n)))
	       (/$ (float csortcar) (float (* n n))))))

;;;;;;;;;;;;;;;

Here's the transcript. The lists of 5 elements are:
	n
	compares for sort
	compares for sortcar
	compares for sort / n*log(n)
	compares for sortcar / n*n


Franz Lisp, Opus 38
-> (load 'test)
t
-> (test 3)
(3 3 6 0.910239226626837 0.6666666666666667)
-> (test 100)
(100 460 9900 0.9988773083774791 0.99)
-> (test 200)
(200 1020 39800 0.9625697456705496 0.995)
-> (test 300)
(300 1440 89700 0.8415468193831012 0.9966666666666667)
-> (test 400)
(400 2240 159600 0.9346629619469353 0.9975)
->