Re: In-place list manipulation

On Nov 22, 8:30 am, "Aki Tuomi" <cmo...@xxxxxxxxxxx> wrote:
When doing mergesort in place, I have ran into a following problem:

How to perform in-place interleave during merge without need of auxilliary
list or array?

I have two sets of indexes: a.start, a.stop and b.start and b.stop. These
contain start and stop indexes in the list where the data is. My question
is, how do I do merge the two into the list in-place?

Example:

List = {1,3,2,5,4,6,7,8,9}

a.start = 1
a.stop = 2

b.start = 3
b.stop = 4

a = {3,2}
b = {5,4}

merge(a,b,List)

List = {1,2,3,4,5,6,7,8,9}

I have solved this now by copying the two segments into temporary arrays and
then copy data back from there, but it does not really feel right. Any
ideas?
On Nov 22, 8:30 am, "Aki Tuomi" <cmo...@xxxxxxxxxxx> wrote:
When doing mergesort in place, I have ran into a following problem:

How to perform in-place interleave during merge without need of auxilliary
list or array?

I have two sets of indexes: a.start, a.stop and b.start and b.stop. These
contain start and stop indexes in the list where the data is. My question
is, how do I do merge the two into the list in-place?

Example:

List = {1,3,2,5,4,6,7,8,9}

a.start = 1
a.stop = 2

b.start = 3
b.stop = 4

a = {3,2}
b = {5,4}

merge(a,b,List)

List = {1,2,3,4,5,6,7,8,9}

I have solved this now by copying the two segments into temporary arrays and
then copy data back from there, but it does not really feel right. Any
ideas?

As Richard said, in-place merge is very complicated except for the
case of linked lists, where the extra space is essentially allocated
in advance as the link fields. I've never seen in-place merging for
arrays implemented in production.

There _is_ a nice little optimization that many implementations seem
to miss. You just begin a merge step by copying out the lower half of
the array to be merged in advance and merge into the target. Ada is
below. If you don't know Ada, blah'First returns the lowest index of
the array blah. Indexing is with parens (as in FORTRAN). The
expression blah(lo .. hi) slices the array blah. List_Type below is a
"typedef" for an array of any ordered type. (digression: Ada is a
lovely language.)

procedure Sort(List : in out List_Type) is
Mid : Positive;
begin
if List'Length > 1 then
Mid := (List'First + List'Last) / 2;
Sort(List(List'First .. Mid));
Sort(List(Mid + 1 .. List'Last));
-- Merge.
declare
Temp : List_Type := List(List'First .. Mid);
P1 : Positive := List'First;
P2 : Positive := Mid + 1;
I : Positive := List'First;
begin
while P1 <= Mid loop
if P2 > List'Last or else Temp(P1) < List(P2) then
List(I) := Temp(P1);
P1 := P1 + 1;
else
List(I) := List(P2);
P2 := P2 + 1;
end if;
I := I + 1;
end loop;
end;
end if;
end Sort;
.

Relevant Pages

  • 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)
  • Re: Translating python to scheme
    ... Scheme has mutation, and there are reasons to use it. ... confusing when considering a 2d array. ... in other languages: Lisp Lists and Vectors. ...
    (comp.lang.scheme)
  • Re: vasam
    ... // Set the size for long lists in records #2 and #3 only! ... Here is the sequel of my previous post "Variable array sizes as members" ... I was given some advice on how to use malloc and realloc in oder to achieve ...
    (microsoft.public.vc.language)
  • Re: Compare the values of two sorted arrays of variable size.
    ... This algorithm does not check for every possible location in each array. ... > contains a double loop where each element of the inner loop is compared ... > Dim lngMaxAIdx ' Upper value of the A list index. ... one of the lists has finished. ...
    (microsoft.public.scripting.vbscript)