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] |
> In applications which work with large amounts of data it is essential > that we can sort the data "in place". Stable algorithms usually > require O(N) extra space First, merge sort does not require extra space when sorting linked lists. It does require extra space when sorting arrays, but only one pointer per record. (When sorting large amounts of data, records are usually much larger than a pointer.) Secondly, this is Scheme. We are supposed to "optimize" for correctness, generality, and ease-of-use, not minor space savings. If sorting needs 10% or even 20% extra space for a work area, who cares? If you do, you are probably willing to spell out unstable-sort or use a more complex interface (such as how to manage buffers). Applications which work with large amounts of data use external sorting algorithms based on merge sort. > and significant extra time to execute. Quicksort has a really fast inner loop, when the comparison is cheap and can be inlined. I.e. it is great for sorting integer arrays with a hard-coded comparison function. Of course that is totally irrelevant for real applications, or for a Scheme sort routine where the comparison is a function parameter. For a library sort routine, do you have real data that merge sort would take "significant extra time to execute?" Aside: I've been reading Richard O'Keefe rail against quicksort on Usenet for the better part of a decade. --Per Bothner Cygnus Solutions bothner@cygnus.com http://www.cygnus.com/~bothner