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?

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


.

Relevant Pages

  • Re: Quicksort pathological behavior?
    ... > arrays) or mergesort. ... First, heapsort works fine for binary trees too, in fact ... secondary key to make heapsort be stable, or copying the whole array to ... time-enqueued is the best way to achieve stable-sort behaviour.) ...
    (comp.programming)
  • Re: Mergesort algorithm for linked lists
    ... In fact he conditionalizes whether it is natural or not. ... To do natural mergesort with arrays requires an auxilary array where item ...
    (comp.lang.c)
  • Re: merge sort
    ... I have to use a function mergesort that takes 3 arguments - an array, ... int[] temp]. ... I dont have a problem with the merge function only with the mergesort. ... "Merging means the combination of two or more ordered files ...
    (comp.lang.c)
  • Re: merge sort
    ... array, its size, and an help array(i.e mergesort(int array, int ... function only with the mergesort. ... the demonstration uses for hashlib. ...
    (comp.lang.c)
  • Re: merge sort
    ... I have to use a function mergesort that takes 3 arguments - an array, ... int[] temp]. ... I dont have a problem with the merge function only with the mergesort. ... "Merging means the combination of two or more ordered files ...
    (comp.lang.c)