Re: In-place list manipulation

On Thu, 22 Nov 2007 15:30:51 +0200, "Aki Tuomi"
<cmouse@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?

Aki Tuomi


It can be done but the process is not simple. I mean it really
is not simple. The known O(n) algorithms are relatively
expensive and take a fair bit of understanding.

Without those, in place merging requires extra space regardless
of whether the subarrays are interleaved or are occupying
contiguous halves.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die
.

Relevant Pages

  • Re: "Interleave" permutation algorithm?
    ... Is there a fast algorithm to compute the "interleave" and ... a,b,c,d are array segments we swap b and c and then process ... explicitly is that algorithm analysis customarily assumes the ... behaves "in the same" way as a real computer. ...
    (comp.programming)
  • Re: "Interleave" permutation algorithm?
    ... Is there a fast algorithm to compute the "interleave" and ... a,b,c,d are array segments we swap b and c and then process ... I think the original request is for Ototal space taken, ... If you code it using recursion, ...
    (comp.programming)
  • Re: "Interleave" permutation algorithm?
    ... different algorithm to interleave an array of pointers to the data ... The in-place algorithm works by rotating a chunk of the array: ... needs to be moved into this position" and rotates it into position. ...
    (comp.programming)
  • In-place list manipulation
    ... 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? ... Aki Tuomi ...
    (comp.programming)
  • Re: random generator for a given period
    ... > that memory seems cheap without being so. ... The efficiency game it all about algorithms and rarely about polishing the code. ... Then you can sort on the random numbers with the array of indices passive. ... So what I'm looking for is a random numbers generator of a given period and with the range equal to the period. ...
    (sci.stat.math)