Understanding Merge Sort algorithms

File: full.png (68KB, 1294x731px) Image search: [Google]

68KB, 1294x731px

heres the full pseudo code

File: 2017-06-17-014708_703x691_scrot.png (53KB, 703x691px) Image search: [Google]

53KB, 703x691px

I'm by no means an expert, but I post the 5-8 pages on my book explaining it if you'd like.

File: 2017-06-17-014716_789x734_scrot.png (130KB, 789x734px) Image search: [Google]

130KB, 789x734px

multiple image posts when?

>>332767
Every help is appreciated. Though I know what mergesort is supposed to do: split up an array until p == r and then merge them while sorting. Easier said than done though. It may also be possible that the mergesort code is off
If you could, please post the pages

File: 2017-06-17-014726_814x872_scrot.png (187KB, 814x872px) Image search: [Google]

187KB, 814x872px

Maybe that broken down algorithm in the last two will help you understand it. If it does you can pay me back here ;)

>>332728

>>332769
>>332768
>>332769
If you want more pages let me know, I can post the whole section on merge but I think that algorithm bit is probably what you're looking after meticulously reading it over. I've only glossed it so far, so sorry I can't be of more help!

File: 2017-06-17-015707_786x542_scrot.png (112KB, 786x542px) Image search: [Google]

112KB, 786x542px

>>332771
last note after algorithm here

>>332771
As for your problem, I can't help you. All of my slides are in german. Again, thanks for the scans

>>332777
of course, if you need anymore let me know, good luck nazi-anon

>>332760
Sounds like a scopus problem to me. If the condition is fulfilled, you will split and merge all of it, not just the first half, since that is still in the scopus. Probably just recursively applied to all elements.
But my basics are a bit rusty so take that with a grain of salt.

>>332760
>But by the time the right side Mergesort(A, p, q) is fully split, the if condition should equal wrong so Mergesort isn't executed.
This is the base case of the recursion. There's always gotta be a base case, otherwise your recursion will never finish. In our case, "base" means p==r (p will never be less than r). You can't sort an array with only one element, so nothing happens - within this function body. However, the parent function call can still take this item and the other side and merge them. You will have *r* times where Mergesort says "uhh there's only one element, so I can't do anything", at which point the calling function can do a merge.

Remember that p,q, and r will be local to each function call in the recursion. You could put the (A,q+1,r) above (A,p,q) and get the same result.

>>332795
So, the base case is never met. Okay.
But how are lines 4 and 5 called? Should it not loop after calling line 3?

And where exactly are the sub-arrays sorted?

>>332798
No, the base case IS met. It's met a total of r times, r being the Top-level r at the very first mergesort call. There's nothing that would cause us to loop or get stuck.

>>332800
How is Merge Sort called again after the base condition is met?
Take a look at this.
This is the pseudo code in better:

if (lowIndex == highIndex)
return;
else {
int midIndex = (lowIndex + highIndex) / 2;
mergeSort(list, lowIndex, midIndex);
mergeSort(list, midIndex + 1, highIndex);
merge(list, lowIndex, midIndex, highIndex);
}
}

The base case is
if (lowIndex == highIndex

hwo do you do any of

mergeSort(list, midIndex + 1, highIndex);

if the base case is met by
mergeSort(list, lowIndex, midIndex);

>>332799
The actual sorting happens in >>332762 lines 13-19. You are taking the two sub-arrays A[p,q] and A[q+1,r], and making a combined new array where you simply pop out whatever number's lower, until you reach the end of both sub-arrays. Then you copy-paste that new array over A[p,r] - bam, that subsection of A is sorted. I'm describing it in a kinda backwards way compared to your image, but the end result is the same.
>>332802
I think I see the crux of the matter. When "return" happens in that base case, it doesn't stop your entire sort - ONLY that one function call. "return" is exactly what allows that second recursive mergesort call to happens, because it means that the first mergesort has stopped. You need to think about it in a larger context than just one function.

>>332805
>The actual sorting happens in >>332762 (You) lines 13-19. You are taking the two sub-arrays A[p,q] and A[q+1,r], and making a combined new array where you simply pop out whatever number's lower, until you reach the end of both sub-arrays. Then you copy-paste that new array over A[p,r] - bam, that subsection of A is sorted. I'm describing it in a kinda backwards way compared to your image, but the end result is the same.

Isn't merge called only once? How do so many merge operations occur then?

>>332896
It's called once for every pair of mergesort calls. Meaning,non-base cases where you have to split your array section in half. By the time the very top-level Merge is called, the two halves of the full array are already sorted via Merges that occurred higher on the stack.