Public Group

# merging 2 parts of a array !!

This topic is 2802 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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
Have you looked at different sorting algorithms?

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

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

##### Share on other sites
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
can you use a temp variable and then swap the numbers?

##### Share on other sites
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
xytor: What if you have 1357 2468? or 1119 1234?

##### Share on other sites
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
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]

1. 1
2. 2
Rutin
22
3. 3
JoeJ
18
4. 4
5. 5

• 17
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631726
• Total Posts
3001910
×