Sign in to follow this  
y2jsave

merging 2 parts of a array !!

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 ..

thanjk in advance
y2jsave

Share this post


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

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this