Re: fast stable sort

On Fri, 14 Nov 2008 19:03:43 -0500, CBFalconer
<cbfalconer@xxxxxxxxx> wrote:

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.

In this case the requirement is to sort the pointers in place
without using an auxilliary linked list. IOW, load the pointers
in an array. That is the requirement; you can't use a linked
list.




Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: fast stable sort
    ... an example program on the use of hashlib. ... How do you load a herd of strings into your ... 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 ... 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 ... 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 ... diddles the pointers, not the strings. ...
    (comp.programming)
  • Re: A taxonomy of types
    ... however, elsewhere in my project (off in the dynamic typesystem, ...), I ... (since I am using NULL-terminated strings), and so I have used U+10FFFF ... remember, C also has things like arrays, funtion pointers, nestable ... int RIL_TypeSmallIntP; ...
    (comp.lang.misc)