Change implementation of MERGE-SORT (and therefore SORT) so that it
authorChris Hanson <org/chris-hanson/cph>
Thu, 16 Mar 2000 17:09:11 +0000 (17:09 +0000)
committerChris Hanson <org/chris-hanson/cph>
Thu, 16 Mar 2000 17:09:11 +0000 (17:09 +0000)
commit5c00b6def9576d61e9c8d5bc7c3fcd0c9c4b5ca1
treeee75b00b53221f05aaeb2f6d0526fd0cddad5493
parent72e3e4805267fe7228ff44d9af606e208649c12d
Change implementation of MERGE-SORT (and therefore SORT) so that it
uses the in-place vector-sorting algorithm for lists.  The previous
algorithm created a stack of depth (/ (LENGTH L) 2), which made it
impossible to use for large lists.  This algorithm creates a stack of
depth (/ (LOG (LENGTH L)) (LOG 2)).

Additionally, tweaked the vector-sorting algorithm to use indexes in a
slightly more efficient (and clearer) way.
v7/src/runtime/msort.scm