Sign in to follow this  
johnnyBravo

Quick merge sort question

Recommended Posts

Hi when using a merge sort with two sorted(ascending) arrays, does it work like this: if (array1[0] < array2[0]) result[0] = array1[0] result[1] = array2[0] else result[0] = array2[0] result[1] = array1[0] endif and so on while iterating the lists, but also what happens when the two arrays are of different sizes eg: 1 4 6 9 1 7 11 a brief description would be fine thanks!

Share this post


Link to post
Share on other sites
Sort of... [grin]. See merge sort.

It's more like

if (array1[0] < array2[0])
result[0] = array1[0]
else
result[0] = array2[0]
endif

The thing is that there's no guarantee that

array2[0] < array1[1]

so just deal with adding one result at a time.

With your sample set

1 4 6 9
1 7 11

it's clear that two items from the top list would be added consequetively. Switching back and forth between the two would leave the result unsorted

1 1 4 7 6 11 9 rather than 1 1 4 6 7 9 11

The algorithm should acount for the possibility of different sized sub arrays.

Share this post


Link to post
Share on other sites
Thanks

This has to be the most confusing sort of them all!, unfortunently i can see why it is useful

I ended up copying the sort on wiki :), i'll learn it better later, sleep time!


vector < int > merge( vector < int > v1, vector < int > v2)
{
vector < int > result;
int ind1 = 0;
int ind2 = 0;

if(!v1.size())
{
return v2;
}

if(!v2.size())
{
return v1;
}

while((ind1 < v1.size()) && (ind2 < v2.size()))
{
if(v1[ind1] <= v2[ind2])
{
result.push_back(v1[ind1]);
ind1++;
}
else
{
result.push_back(v2[ind2]);
ind2++;
}
}

while(ind1 < v1.size())
{
result.push_back(v1[ind1]);
ind1++;
}

while(ind2 < v2.size())
{
result.push_back(v2[ind2]);
ind2++;
}

return result;
}


Share this post


Link to post
Share on other sites
Quote:
Original post by johnnyBravo
This has to be the most confusing sort of them all!,
What makes you say that? I know a number of far more difficult to understand sorts. e.g Smoothsort.
Quote:
unfortunently i can see why it is useful
Yes, very much so, although it has it's downsides also.
Quote:
I ended up copying the sort on wiki :), i'll learn it better later, sleep time!
Make sure you do, especially if this was for some coursework. It's really simple if you break it down into little steps. I suggest writing comments throughout the algorithm, as you work out what each bit does, then if you like, you could post it with comments later, to see if your understanding is correct.

Share this post


Link to post
Share on other sites
Not difficult at all: just try it yourself.

Take a deck of cards and split it into two piles of unequal size, and sort each however you like. Then put them face down and turn up one card from each. By iteratively taking the top card from either (and choosing correctly - but it will be obvious how from just trying it) and putting them onto a new pile, you will end up with a totally sorted deck. Unevenness in size is no problem: if you *can't* take from one deck (because it has run out), then obviously you just take from the other.

Now try shuffling the deck and doing all the sorting this way, recursively. :)

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