Re: sort bug

[Taiichi Yuasa <yuasa%tutics.tut.junet%utokyo-relay.csnet@RELAY.CS.NET>]

	Date: Mon, 4 Jan 88 18:41:59 PST
	From: raible%orville.arpa%sally.utexas.edu@RELAY.CS.NET L. Raible" <raible@orville.arpa>
	Message-Id: <8801050241.AA26786@orville.nas.nasa.gov>
	To: kcl@rascal.ics.utexas.edu
	Subject: sort bug

	>(sort '(2 1) #'<)
	(1 2)

	>(sort '(2 1) #'<=)
	(1 2)

	>(sort #(2 1) #'<)
	#(1 2)

	>(sort #(2 1) #'<=)

	Error: Value stack overflow.
	Error signalled by SORT.

	Broken at SORT.  Type :H for Help.
	>>

	Has anyone else seen this?  Does anyone have a fix for this?
	Hint: the bug is in quick-sort (lsp/seqlib.lsp).

	- Eric


There was a bug in the definition of the Lisp function QUICK-SORT
in file lsp/seqlib.lsp.  To fix the bug, use the following definition
and the associated proclamation.

(proclaim '(function quick-sort (t fixnum fixnum t t) t))

(defun quick-sort (seq start end pred key)
       (declare (fixnum start end))
  (if (<= end (the fixnum (1+ start)))
      seq
      (let* ((j start) (k end) (d (elt seq start)) (kd (funcall key d)))
            (declare (fixnum j k))
        (block outer-loop
          (loop (loop (decf k)
                      (unless (< j k) (return-from outer-loop))
                      (when (funcall pred (funcall key (elt seq k)) kd)
                            (return)))
                (loop (incf j)
                      (unless (< j k) (return-from outer-loop))
                      (unless (funcall pred (funcall key (elt seq j)) kd)
                              (return)))
                (let ((temp (elt seq j)))
                  (setf (elt seq j) (elt seq k)
                        (elt seq k) temp))))
        (setf (elt seq start) (elt seq j)
              (elt seq j) d)
        (quick-sort seq start j pred key)
        (quick-sort seq (1+ j) end pred key))))


-- Taiichi