Re: sort a generic linked list?

"Michael A. Covington" <look@xxxxxxxxxxxxxxxxxxxxxx> writes:

Linked lists are inherently not sortable without a lot of extra work
linking and unliking things. Arrays are very sortable.

Well, as pointed out also by Jon Skeet, linked lists can be sorted
using mergesort in worst-case time O(n log n), without extra memory,
and stably (not changing the order of equal elements). In many
respects this provides better functionality than quicksort on arrays.

The C5 collection library for C#/.NET has such an sorting
implementation for linked lists; http://www.itu.dk/research/c5/

Peter
.

Relevant Pages

  • Re: Questions on Using Python to Teach Data Structures and Algorithms
    ... linked lists produces cache misses rather often, ... arrays do not. ... Small dynamic arrays are faster than linked ...
    (comp.lang.python)
  • Re: C++ vs. .net
    ... > in one of my C++ applications, I have quite a big amount of data ... > (linked lists, arrays, variables, ...) that I'd need to pass to a ...
    (microsoft.public.vc.language)
  • Re: Dinamically allocate array of array of structures
    ... I am able to do it for myfiles, but not with mydirs. ... Pseudo-code is ok. ... If this is not so simple I will use static arrays. ... Linked lists and arrays are very different things. ...
    (comp.lang.c)
  • Re: "Dumb Debugginging on the Mainframe"
    ... "Years ago, with procedural languages, we used things like loops, function ... calls, arrays, linked lists, queues and stacks. ...
    (bit.listserv.ibm-main)
  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... How do you load a herd of strings into your ... in an array. ... place sorting/merging linked lists are irrelevent because they ...
    (comp.programming)