# Quick merge sort question

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

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

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 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 on other sites
Quote:
 Original post by johnnyBravoThis 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 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. :)

• 33
• 12
• 10
• 9
• 9
• ### Forum Statistics

• Total Topics
631353
• Total Posts
2999488
×