Re: In-place list manipulation

On Nov 22, 6: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?

Aki Tuomi

With linked lists, auxilary lists are inexpensive. Essentially, you
Splice elements from one list into the other. The splicing simply
changes pointers, so no data is actually moved. Simply splice into the
auxilary until it contains elements of both lists, then splice the
result into one of the originals.

It should require no additional memory. You will find it to be faster
than in-place, as well.

Otherwise, you have to maintain the end of the merged portion E,
starting before the the first item. When the other list's item comes
first, splice/insert at E, otherwise just move the end forward. Be
aware that this modifies both lists.

If you are dealing with contiguous memory, good luck! It will be slow.
.

Relevant Pages

  • Re: Effective STL Item 4 (size() vs. empty())
    ... >> Any other practical obstacle you have been encountering? ... The Osize leads to an Osplice ... source and destination lists are the same, ... to be able to keep iterators to specific items. ...
    (comp.lang.cpp)
  • Re: Adding functions to generic package
    ... Just splice the element prior to the distinguished iterator value Back: ... Why isn't there a Swap function in the library like ... the nodes on the internal linked lists of a single list container. ... The list container has both of the these operations, ...
    (comp.lang.ada)
  • std::list::size
    ... >> where this was hashed out was that constant time splicing was more ... > whole lists, or using splicing to rearrange a single list, which must cover ... Search it for uses of splice. ... Complexity: Constant time. ...
    (comp.lang.cpp)
  • Re: random array elements and speed
    ... initial elements JJ> then yeah the splice method might well be two or ... swapping and pop will blow that away for large lists. ... is even on moderately large arrays. ... Overwrite the chosen element with the last element, ...
    (comp.lang.perl.misc)
  • Re: Questions about destructors on std library containers
    ... >> With these implementations splice() is faster because they don't ... > sizeto be Oand allows splice on different lists to be O. ... constant complexity", it requires that splice has complexity ...
    (comp.lang.cpp)