This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: stable sorting


> Is it easy to provide something similar for guile?

Yes.  Use merge sort.  Guaranteed O(n log n), and stable,
neither of which is true for quicksort.

Heapsort is also guanteed O(n log n), but is not stable.

Merge sort is especially good for sorting lists.

The main practical advantage of quicksort or heapsort is that
neither requires extra memory when sorting arrays.  I don't believe
that is an issue when sorting lists.

The new Java collections framework uses merge sort.  See:
http://www.javasoft.com/products/jdk/1.2/docs/api/java/util/Collections.html#sort(java.util.List)
(Note that when they say "List" they been abstract sequence, not
necessarily a linked list.)

	--Per Bothner
Cygnus Solutions     bothner@cygnus.com     http://www.cygnus.com/~bothner