//This is an annotation of the code that they provide for merge. void merge(int A[], int low, int high, int mid) { //We meed c[50] to put our sorted data into. This is as we need to maintain the order of A[] until the end of the function //A[] is passed by reference as its an array (pointer), so in this application all merge() calls share A[]. // I & J are indexes for each half of the array section to be merged. In this function I & J will move right. // k is the index to which we are writing to in the temporary array c[50]. (This merge will not work on array size > 50 lol.) int i, j, k, c[50]; i = low; k = low; j = mid + 1; //We have two sorted subsections in merge sort, so we need to determine which values to copy, take the example of: // [0,2, 1,3] where each half of the array are independently sorted. here we can merge the array by looking at the beggining of each // section and only reading the next value of a section if the last value read was lower. IE. read 0 and 1, 0 is lower so we write 0 to our result. r = [ 0 ? ? ? ?], then we read 2 and 1, 1 is lower so we write 1 and r = [ 0 1 ? ?], then we read 2,3 and 2 is lower so we write this to our result r = [0 1 2 ? ] then we have 3 left which this while loop doesn't handle, but the next does. while (i
@@sidiousvic Sorry but I am not quite sure I follow what you mean by uneven. The main requirement of the code is that both regions given to merge are sorted. The code should run if you give it uneven arrays as I will explain, but in the execution of the algo. as shown it is called with typically even arrays as inputs. Given this The function should work even if we feed it two sections containing [1,5] and [2,3,4,6,7,8,9] as the first loop terminates once c looks like [1,2,3,4,5] or so the second loop is skipped and the third loop moves the remainder such that c looks something like [1,2,3,4,5,6,7,8,9] It has been a bit since i looked at it closely, but as the first loop does not really 'take turns' and the other two loops are for handling excess I believe the code should run on uneven sets. So the first loop runs until only one array is left then one of the remaining loops copies the rest from that array The biggest Issue I have with this code is how it allocates memory that prevents it from sorting any set of a large size
I already know how merge sort works, just forgot how to merge. I was watching this video and expecting he to explain merge() so honestly I was a little bit triggered when he just showed that "magic" gif.
This is one of the best tutorial videos I have ever seen - thanks to you I got to understand the recursion as well as the merge sort algorithm, so you killed two birds with one stone. Great work!
this video should be on top because other are just explainging code and i wonder how htey even explain when they didnt understand as well so this video should be on top
What happen when you divide an array? Does it makes two different new arrays everytime with splitting elements? Does it mean we are assigning every splited to a new array?
When the mergesort() on left statement returns then it should call mergesort on right part naa? Why it calls merge() instead of mergesort() on remaining right part of array?
I am not understanding the recursive call.say when merge_sort(low,mid) is called until low ==high ,reaching a single element, Then merge_sort(mid+1,high) is called and then mid+1 will be 1 like merge_sort(1,high) bcz from previous recursive func we get mid as 0. And this where I am confused about how it does really execute.
at the end of the first recursive call i.e., when low = 0, high = 1 and mid = 0, the function returns and the next mergesort for the second half is called. Remember at this point the values are low = 0, high=1 and mid =0 so the call would be mergesort(mid+1, high) = mergesort(1, 1) which would immediately return since 1 = 1.. and this follows.
//This is an annotation of the code that they provide for merge.
void merge(int A[], int low, int high, int mid)
{
//We meed c[50] to put our sorted data into. This is as we need to maintain the order of A[] until the end of the function
//A[] is passed by reference as its an array (pointer), so in this application all merge() calls share A[].
// I & J are indexes for each half of the array section to be merged. In this function I & J will move right.
// k is the index to which we are writing to in the temporary array c[50]. (This merge will not work on array size > 50 lol.)
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
//We have two sorted subsections in merge sort, so we need to determine which values to copy, take the example of:
// [0,2, 1,3] where each half of the array are independently sorted. here we can merge the array by looking at the beggining of each
// section and only reading the next value of a section if the last value read was lower. IE. read 0 and 1, 0 is lower so we write 0 to our result. r = [ 0 ? ? ? ?], then we read 2 and 1, 1 is lower so we write 1 and r = [ 0 1 ? ?], then we read 2,3 and 2 is lower so we write this to our result r = [0 1 2 ? ] then we have 3 left which this while loop doesn't handle, but the next does.
while (i
You're a fucking champ 🍻
One question though, this doesn't seem to work for uneven arrays. Why would that be?
@@sidiousvic Sorry but I am not quite sure I follow what you mean by uneven. The main requirement of the code is that both regions given to merge are sorted. The code should run if you give it uneven arrays as I will explain, but in the execution of the algo. as shown it is called with typically even arrays as inputs.
Given this The function should work even if we feed it two sections containing [1,5] and [2,3,4,6,7,8,9] as the first loop terminates once c looks like [1,2,3,4,5] or so the second loop is skipped and the third loop moves the remainder such that c looks something like [1,2,3,4,5,6,7,8,9]
It has been a bit since i looked at it closely, but as the first loop does not really 'take turns' and the other two loops are for handling excess I believe the code should run on uneven sets. So the first loop runs until only one array is left then one of the remaining loops copies the rest from that array
The biggest Issue I have with this code is how it allocates memory that prevents it from sorting any set of a large size
I wish this comment achieve more likes than the video itself
I was scratching my head about how the recursive actually work for this algorithm. Now, it is clear. Thank you!
Thank you very much, two recursions in one function make me confused a while. This video is fantastic.
Excellent interpretation of recursion with stack visualization.
I was struggling to do the merge part until I found your video and understood how to do it. Thanks a lot, really! And just keep coding :)
Best representation of call stack for merge sort. Much appreciated.....🙌🙌
Great video, thank you very much ❤
Doesn’t explain how the merge function does the actual sorting ...
Yeah wtf
I already know how merge sort works, just forgot how to merge. I was watching this video and expecting he to explain merge() so honestly I was a little bit triggered when he just showed that "magic" gif.
This is video is only for mergeSort visualisation.
Thankyou very much. It helped me a lot.
Thank you for the video! Its visualization really helps for better understanding of recursion.
This is one of the best tutorial videos I have ever seen - thanks to you I got to understand the recursion as well as the merge sort algorithm, so you killed two birds with one stone. Great work!
The video explanation is phenomenal just which call stack.
this video should be on top because other are just explainging code and i wonder how htey even explain when they didnt understand as well so this video should be on top
Lets just all appreciate how CONCISE this code is compared to other merge sorts.
Thank you very much ❤ ... Excellent interpretation.
Front end trying to dive into back. This video helped.
What happen when you divide an array? Does it makes two different new arrays everytime with splitting elements? Does it mean we are assigning every splited to a new array?
Yes we divide each array into 2 different arrays
Great visualization, thank you, sir.
Thanks a lot! Finally understood how the recursion actually works!
Thank you so much! This was really helpful!
wow good work.you visualize how recursive work.thank you
thanks alot sir........ your learning is incredible 😍😍
When the mergesort() on left statement returns then it should call mergesort on right part naa?
Why it calls merge() instead of mergesort() on remaining right part of array?
Awesome tutorial!
I am sorry but this is not called an explanation. It's a gentle introduction...
Why is this a gentle introduction and not an explanation?
thank you so much, it's helpful
Don't understand how that final two sub arrays suddenly get merged together sorted
i want to know ;how exactly does the merge method works?
May i know how u did these graphics?
PowerPoint! It’s a very accessible solution for things like this, but admittedly annoying to record over.
Thanks !!Great VIDEO.... It's really easy and helpful to understand how recursion works . Pls keep uploading like this>>>>>
sorry but how I find steps? when teacher said write the steps which line is step?? he gave the number of example
Can you post the merge(A, low, high, mid) function code in the description? I want to see the logic for the merge function
pastebin.com/bpiMpDxx
Ah thx
thanks for this video with stack. i get it !:)
I am not understanding the recursive call.say when merge_sort(low,mid) is called until low ==high ,reaching a single element,
Then merge_sort(mid+1,high) is called and then mid+1 will be 1 like merge_sort(1,high) bcz from previous recursive func we get mid as 0.
And this where I am confused about how it does really execute.
i have the same doubt........can you please explain if the doubt is clarified by now?
at the end of the first recursive call i.e., when low = 0, high = 1 and mid = 0, the function returns and the next mergesort for the second half is called. Remember at this point the values are low = 0, high=1 and mid =0 so the call would be mergesort(mid+1, high) = mergesort(1, 1) which would immediately return since 1 = 1.. and this follows.
muchas gracias y buena explicacion.
very helpful,thanks a lot!
which tool did you use to create these graphics?
how to run this code
can anyone explain why h is array size-1?
Can I please get the source code of the demonstration? I needed it for my college project
good
well done!!
This is great, thank you!
ty
please give some codes to practice with and be smooth with it
great work sir
interesting ...
even this person is saying "sort" as "sword"
You need your ears checked mate.
Your voice is like Mark zuckerberg xD
That’s unfortunate
lol "Just keep coding"
Will do.
genant
This video is terrible