Re: fast stable sort

Richard Harter wrote:
CBFalconer <cbfalconer@xxxxxxxxx> wrote:
pete wrote:
Richard Harter wrote:

There are in place stable versions of mergesort.

Can you post C code for a stable in place mergesort function?

Such exists in wdfreq.c, an example program on the use of hashlib.
wdfreq has been put in public domain, hashlib is released under
GPC. See:

<http://cbfalconer.home.att.net/download/hashlib.zip>

The context is in-place with O(1) extra storage; use of an
auxilliary linked list is not on the table.

How do you load a herd of (variable length) strings into your
system without at least an auxiliary table of pointers to the
individual strings? Once you recognize this, the obvious way to
load the strings is with a singly linked list. The total memory
usage will normally be less. Note that the sort only diddles the
pointers, not the strings.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
.

Relevant Pages

  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... wdfreq has been put in public domain, hashlib is ... How do you load a herd of strings into your ... diddles the pointers, not the strings. ...
    (comp.programming)
  • Re: Hash function of structs
    ... Alexander has keys which are not strings ... Chuck's hashlib handles strings, so you will need you to code ... your own routines to handle your keys. ... Chuck's overly complex interface will ...
    (comp.lang.c)
  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... wdfreq has been put in public domain, hashlib is ... How do you load a herd of strings into your ... diddles the pointers, not the strings. ...
    (comp.programming)
  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... wdfreq has been put in public domain, hashlib is ... How do you load a herd of strings into your ... In this case the requirement is to sort the pointers in place ...
    (comp.programming)
  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... wdfreq has been put in public domain, hashlib is ... How do you load a herd of strings into your ... In this case the requirement is to sort the pointers in place ...
    (comp.programming)