# merging 2 parts of a array !!

## Recommended Posts

y2jsave    100
Hi folks,

given a array .
its first half is sorted .
its second half is sorted .

now we have to sort the complete array . in place . we cant use a new array to store the result ..

y2jsave

##### Share on other sites
stone_ta    126
Have you looked at different sorting algorithms?

##### Share on other sites
xibo    110
In particular, you should take a look at the merge sort algorithm.

http://en.wikipedia.org/wiki/Merge_sort

##### Share on other sites
y2jsave    100
but the problem is that we cant create a new array to save the final sorted array ..

so i dont know how to apply merge sort ..

however , i feel that a modified version of merge sort may be used here .. which i tried to think but could not

##### Share on other sites
stone_ta    126
can you use a temp variable and then swap the numbers?

belfegor    2834

##### Share on other sites
xytor    136
nah, just compare the first element and the element just after the half point.
if the first element is bigger, do an in-place swap:

6789 1234
1789 6234
1289 6734
1239 6784
1234 6789
done!

OR

1234 6789
done!

##### Share on other sites
Nypyren    12062
xytor: What if you have 1357 2468? or 1119 1234?

##### Share on other sites
xytor    136
Then you would need to do an in-place merge, something like this perhaps:
http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html
or this
http://www.cs.ubc.ca/~harrison/Java/MergeSortAlgorithm.java.html

##### Share on other sites
1863    126
Off the top of my head:

for (int f = 0; f < first.size(); ++ f){    for (int s = second.size() - 1; s >= 0; -- s)    {        if (second[s] < first[f])        {	    int temp = first[f];	    first[f] = second[s];	    second[s] = temp;        }    }}

Edit: Even better!

Also, if your halves aren't pre-sorted, you can sort them after doing the above. As an alternative to using the temp variable you can use the XOR method or swapping in place.

Edit2: (vvvvvv) Bah, I misread the question as needing to sort two separate pre-sorted arrays in place as if they were one. Obviously this is O(n^2) and doesn't apply if it's one array. Oh well, I had fun thinking about it =P

[Edited by - 1863 on November 14, 2010 7:11:40 PM]

##### Share on other sites
Antheus    2409
In-place merge sort is non-trivial to implement. It also has complexity of nlogn.

Just run regular quick sort (std::sort or such) over the array.

Quote:
 Off the top of my head:
That is n^2 algorithm, it's better to just fully resort the array using heap or quick sort.

##### Share on other sites
SiCrane    11839
In this case you don't need to do the full merge sort, just run the last step of the algorithm.