Re: fast stable sort

Mark Wooding <mdw@xxxxxxxxxxxxxxxx> writes:

Tim Rentsch <txr@xxxxxxxxxxxxxxxxxxx> wrote:

About doing a truly in-place mergesort for linked lists -- I don't
think it's conceptually difficult, but (after thinking about how to do
it) I sure wouldn't want to program it. :)

I think Simon Tatham's algorithm seems quite straightforward.

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

It doesn't do anything hairy with the links at all.

I agree, as informal descriptions go, it's not bad. It does tend to
gloss over the mechanics of element counting and handling of limit
cases, which aren't terribly hard to get right but also aren't
terribly hard to get wrong; for this kind of algorithm those kinds
of errors often lead to incomprehensible catastrophic failure.

Despite my insalubrious comment, thank you for the reference (and also
thanks to Richard Harter for his suggestion on this, I forgot to say
that in my earlier message).
.

Relevant Pages

  • Re: Breaking .NET Compact Framework code - how easy is it
    ... I think what Ginny is saying is put the algorithm in the C++ unmanaged ... if this call fails then the calling C# ... could even perform some unnecessary processing during this comparison stage ... >> Simon, ...
    (microsoft.public.dotnet.framework.compactframework)
  • Re: Dynamic "One-time-pad"
    ... > Sorry Erich, ... > description your algorithm. ... > ability to give your paper to a programmer who knows nothing of ... Hallo, dear Simon, ...
    (sci.crypt)
  • Re: AES and dynamic table generation
    ... terms of increased security of the algorithm. ... I'd imagine one use might be so that the tables don't have to be ... Simon ...
    (sci.crypt)
  • Re: Shamir sharing and GF(2^n)
    ... Mark Wooding wrote: ... Lenstra's elliptic-curve factoring method which seems to work well ... less than some bound using ECM, ... in the algorithm. ...
    (sci.crypt)
  • Re: Fast Binary-to-Decimal Conversion Algorithms?
    ... Simon G Best wrote: ... > Without much success, I've been trying to find a 'fast' algorithm ... > for converting large numbers from binary to decimal. ...
    (comp.programming)