How to merge the later half of an array into the first half one by one?

Question

Suppose we have an array which contains 2m elements. we can divide the array into two parts, the first one and the later one. My question is how to insert the later part of the array into the first part one by one, for example the array

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

after merge we have the new array

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

I know some method to to this such as use another buffer to store the temp data, but it is required that the space complexity should be O(1).

My question is whether there exist an optimized method with O(n) time complexity and O(1) space complexity?

This is answered on CS stack exchange [here](http://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array). — interjay, Oct 29 '14 at 14:44

score 0 · Answer 1 · answered Oct 29 '14 at 14:32

0

It can be done with 2 temp variables, suppose the array is {1,2,3,4,5,6,7,8,9,10}

1: You start off by having 2 pointers, temp1 at the starting and temp2 at the halfway (at 6)..

2: You store value of temp1 i.e.1 at first place in the array, and let temp1 have the value of the second element, i.e.2

3: Similarly you store temp2 i.e.6 in the next place in the array, and let temp2 have the next value, i.e. 7..

Continue this until temp1 reaches halfway and temp2 reaches the end, and you would get the results as you desired..

answered Oct 29 '14 at 14:32

Haris

12,120
6
43
70

1

It fails as soon as the second iteration, unless you better explicit how you move the pointers and store the values. – fjardon Oct 29 '14 at 14:37
@fjardon: why will it fail in the second iteration? – Haris Oct 29 '14 at 14:38
1

It doesn't work because the values you copy from the second half would overwrite the values in the first half. – interjay Oct 29 '14 at 14:39
@interjay: you are interpreting the algorithm wrong, gimme a minute, will write the code and post.. – Haris Oct 29 '14 at 14:40
Every step you need one temp variable more, therefore the space complexity is not O(1). – a_guest Oct 29 '14 at 14:44

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

If at all possible, your best route is to simply define an iterator that does the addressing in the correct order, so you can leave all the data in place, and just change the order in which you address it.

If you can't do that, you obviously need an in-place merge. The cleanest explanation I've found of in-place merging is in an article on Dr. Dobbs. Like most such papers/articles, this is written assuming that the intent is to do the merging as part of the implementation of a merge sort. As such, it's written in terms of finding the ranges of values that fit a sorting criteria. In your case, that part doesn't apply--you just want to merge the two halves with what you might think of as perfect interleaving, so you it's trivial to just select ranges based on placement rather than searching for the correct places based on comparing values. The operations for merge itself are done identically though.

How to merge the later half of an array into the first half one by one?

2 Answers2

Bibliography