Re: In-place algorithm

On Thu, 29 May 2008 19:43:07 -0400, CBFalconer
<cbfalconer@xxxxxxxxx> wrote:

Richard Harter wrote:
CBFalconer <cbfalconer@xxxxxxxxx> wrote:
{snip]

Nobody has been talking about sorting an array. Unless I have
missed something, this has been about sorting lists from the
original post. Yes, you can store a list in an array, but that is
not suitable for sorting without at least doubling the memory
usage. Making a real list requires only one pointer per item.

The original post did not specify whether the subject was arrays
or lists. The original poster followed up with another post
pointing to some specific code at

http://groups.google.it/group/comp.lang.c/msg/c17d9facda50ab57

which is the code for a recursive mergesort on a doubly linked
list. Judging from the comments few people actually looked at
the followup reference. Most of the comments are in a subthread
started by Stephen Howe which I shall quote:

"I am assuming you are taliking about arrays. No. Auxilary
memory is required. Merge sort an be in-place but it is
extremely difficult problem, particularly if you want it to
remain stable. It usually costs O(N * log N * log N)
in-place. There has been some progress over the years but not
to the extent that inplace merge sort is as efficient as merge
sort with auxilary memory.

If you are talking about linked lists, then the links
themselves can be manipulated, no auxilary memory is
required."

Stephen (modulo typos) was quite correct. So, some people in the
thread were talking about both arrays and lists, and, to be fair,
most were talking about sorting lists. However, both on the
table, and if one is talking about mergesort, both should be on
the table.

That said, the original question with its clarification does not
make sense. The term, in-place, only really makes sense in the
context of sorting arrays. When sorting arrays the data is
moved. In-place means that the data is rearranged without using
other than O(1) additional storage. When sorting lists nothing
is moved; the only thing that happens is that pointers are
altered.

What does make sense is to talk about how much memory is used.
Lists intrinsically use O(n) extra memory. Recursion typically
uses O(log n) extra memory. The naive merge algorithm uses O(n)
extra memory; there are merge algorithms that use O(1) extra
space but they are more of theoretical interest than practical
interest.

Your comment does raise an interesting question. We may grant
that it does not make sense to convert a list into an array, sort
the array, and then relink the sorted array. What about doing
the other way around? That is, what about converting an array
into a list, doing a list based mergesort, and then permuting the
array using the list? Yes, that can be done. The catch is that
for large n you run into caching issues.

Note 1: If the data items are large compared to pointers, the
extra space for the naive array merge will be larger than the
extra space for links.








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 linked list
    ... > amounts of memory rather than huge chunks of it. ... random insertions into a vector/dynamic array are not as slow ... to cause a cache miss. ... some hard numbers on speed differences between lists and arrays. ...
    (microsoft.public.vc.mfc)
  • Re: Fast linked list
    ... > amounts of memory rather than huge chunks of it. ... random insertions into a vector/dynamic array are not as slow ... to cause a cache miss. ... some hard numbers on speed differences between lists and arrays. ...
    (microsoft.public.vc.language)
  • Re: In-place algorithm
    ... I suspect CBFalconer has missed the discussion about "extra ... between in-place sorting of an array and in-place sorting of a ... Nobody has been talking about sorting an array. ... this has been about sorting lists from the ...
    (comp.programming)
  • Re: garbage collection problem in large linked lists
    ... Instead all buckets are allocated at once in an array. ... VG.net, which must be very scalable, but only for lists which would normally ... Linked lists require pointer dereferencing in order to traverse. ... When you run out of space, you allocate a new smaller array. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Dict sharing vs. duplication
    ... array to enforce unique keys and I use lists to enforce order. ... API in a page or two of Tcl code, it isn't so much a missing feature ... OpenACS database API which creates a new specialized data structure, ...
    (comp.lang.tcl)