Merge Sort | C Programming Example
Вставка
- Опубліковано 28 лип 2024
- How to implement the merge sort algorithm in C. Source code: github.com/portfoliocourses/c.... Check out www.portfoliocourses.com to build a portfolio that will impress employers!
See Merge Sort Algorithm Wikipedia article: en.wikipedia.org/wiki/Merge_sort - Навчання та стиль
I know you probably hear this a lot but you have THE best C tutorials on the youtube. And trust me I've seen a lot of those studying for final exam of C. Always so clear and well explained
Thank you so much for the kind words Viny, I really appreciate that, hearing feedback like that is very encouraging for me to keep making videos. :-) And good luck on your final exam!
This is the type of explanation I was looking for while trying to learn merge sort!
I'm glad to hear that! I hope it is helpful to people. :-D
Damn, this is the first time I'm watching a merge sort tutorial that doesn't make my mind go crazy but makes everything crystal clear! would love to go through all your DSA courses.
I'm glad to hear it made things crystal clear for you! 😀 I've got UA-cam videos for other sorting algorithms like Bubble Sort, Insertion Sort, Quicksort, etc. They should be under this playlist here: ua-cam.com/video/sepK5w4Uep0/v-deo.html. I've also got a Udemy course on Linked Lists in C: www.udemy.com/course/linked-lists-with-c/?couponCode=JLDEAL22.
I don't even look at what I need on YT anymore, I just go straight to your channel. Here's the crazy part, I'm using this to actually learn problem-solving in JS. But, I have some background in C++, so I can follow along just fine. Thank you so much! Also, please make videos on more advanced algorithms like BFS, DFS, Dijkstra's, Dynamic Programming, etc. You can turn that into Udemy courses even. Would buy it in a heartbeat.
For sure, I've never met such explaination since I started learning to code. Every single letter is explained... There's nothing to be said, this is just awsome!
Thank you very much for the kind words! I'm glad to hear you enjoyed the video. 😀
Wow, this is awesome. I love how you visualized the 3 countervariables with comments.
Thank you for the kind words Omar, I'm glad to hear that you enjoyed the video and the visualization! :-D
Easy to find, easy to listen easy to understand. Thank you.
You're welcome Wojciech, I'm glad you enjoyed the video! :-)
Thank you SO MUCH. Absolutely amazing content, I really appreciate the time you spent on that, you’re making a big difference :)
You’re very welcome Breno! I’m glad to hear you enjoy the content. :-)
@@PortfolioCourses
#include
void merg_sort(int arry[],int len);
void merg_sort_recursion(int arry[],int l, int r); //l :left portion , r :reight
void merg_sorted_arry(int arry[],int l,int m, int r); //l :left portion , r :reight , m :middel of arry.
int main()
{
int arry[] = {9 , 5, 7, 8, 1, 0, 6, 3, 4, 2};
int len = sizeof(arry) / sizeof(arry[0]);
// printf("number of element : %i
",len);
merg_sort(arry , len); // array actualy sorted.
for (int i=0 ; i < len ; i++)
printf("%d ",arry[i]);
printf("
");
return 0;
}
void merg_sort(int arry[],int len)
{
merg_sort_recursion(arry , 0 , len-1);
// 0 = index left side, (len-1 )= index right side
}
void merg_sort_recursion(int arry[] , int l , int r) // where r=len-1
{
if (l < r)
{
int m = l + (r-1) / 2; // middel index of arry.
merg_sort_recursion(arry ,l , m); //sorted index left side
merg_sort_recursion(arry, m+1 , r); //soorted index right side
merg_sorted_arry(arry,l,m,r);
}
}
void merg_sorted_arry(int arry[] ,int l ,int m , int r)
{
int left_length = m - l + 1;
int right_length = r-m ;
int temp_left[left_length];
int temp_right[right_length];
for (int i=0 ; i< left_length ; i++)
temp_left[i]=arry[l+i];
for (int i=0 ; i< right_length ; i++)
temp_right[i]=arry[m+1+i];
int i , j ,k ;
for (i=0 , j=0, k=l ; k= right_length || temp_left[i]
I can tell you worked really hard to make that visual demonstration in text :) , but I love your videos, I bought one of your courses and it helped me a lot. Thank you.
You're very welcome! :-)
A very helpful explanation thank you very much! Really appreciate the actual process explanation through the comments.
You're welcome Ram, I'm really glad that you found the explanation helpful! :-)
First free video which actually explains this algorithm well 😃
I'm glad you thought the video explained the algorithm well. :-)
This has been a huge help for me!
Awesome, very glad to hear that! :-)
Very clear explanation. Thanks again! :D
You’re welcome! :-D
Man I love the last part! Thank you!
You’re welcome Ali! :-)
Hi, I wonder if in function merge_sort_recursion, the condition must be l < r? As my understanding, when the array is divided into sub-arrays with 1 element, you get l = r, there is no scenario such that l > r. So should the condition in merge_sort_recursion be just l == r? Please correct me if I'm wrong.
i had to watch this this video almost 6 time to install concept into my brain, thankyou for amazing video's.
Merge Sort is a tough algorithm, I’m glad you got it figured out, and you’re very welcome! :-)
hmmm... visual studio compiler doesn't let to create static arrays with variables. That's strange
Awesome explanation and great example. Thank you very much. :D
You’re very welcome, I’m glad you enjoyed it! :-)
thank you for the explanation. It's very clear.
5:28 omg I confounded r-l with r-1 and that's why the program always resultet in an infininite loop. I also didn't get "why is it r-1 ??" This little mistake forced me to debug for hours. But now I understand every little detail of merge sort. Thanks for the video :)
I'm glad you figured it out! And you're welcome Denis! :-D
ikr, tthey wrote l + (r-l)/2 at 5:26 it confused for a sec and thought why didnt he just write (r+l)/2? is there a reason for this long form ;-;
really wonderful explanation! Subscribed.
I’m glad you enjoyed the explanation, and welcome aboard! :-)
it all makes sense now, i feel enlightened.
That’s awesome! :-)
Nice video! It helped me a lot with a college proyect :)
Awesome, that's great to hear José! :-D
what editor are you using and what them are you using, it look so nice
thx it was a brilliant explanation, bravo
You're welcome Théodore! :-D
Thanks a lot for your explanation
You’re very welcome! :-)
Such a good explanation, thanks a lot! :)
You're welcome Raul, I'm glad you enjoyed it! :-) I'm watching this video on your channel now about your trip to Peru & Bolivia, the editing is fantastic.
@@PortfolioCourses Oh cool, haha thanks!
great work, thank you! :)
You’re welcome Frank! :-)
man, you're really really good.
Awww thanks for the very kind feedback! :-)
Clear explanation
I’m glad you enjoyed it Thong! :-)
How can it be true to say temp_left[left_length]?? i think size of the array can't be vaiable
In modern versions of C like C99 it can, only in old versions of C can we not do that. :-)
Good day Sir.
I have a weird question. I understand how this Merge sort works. But there are some tricky lines of code.
So, the question. Am I supposed to know it by heart as a soft developer? I mean type the code without any prompts from the scratch.
Great question! I would say: no, definitely not. 🙂 There's a lot of software developers that don't know how merge sort works, or maybe haven't even heard of it either. And even among software developers that know merge sort, very few could just write it "off by heart", they would probably need to remember how it works and read up on it a bit too. But after reading it up on it to understand how it works, I'd say that most good software developers would be able to describe how it works on a whiteboard and implement the algorithm in some language... they might need to do some trial-and-error coding to get it working right and look at pseudocode code online, but a good software developer should be able to implement it 'with the help of looking at some resources'. That's just my opinion though, I think some great developers might have different opinions that are also valid as well. 🙂
Thank you so much for this video, now I understand this algorithm better.
In 10:34 you mention, that both of the subarrays have been sorted, however i dont quite understand when the sorting really happend. For me it seems like the only time the array is starting to get sorted, is when both subarrays get merged in 13:41. Thats where you compare the values of each index. But like when does the sortting start within the subarrays?
I also have another question regarding the function merge_sort_recursion in 07:03 How will the compiler come to the line merge_sorted_arrays(a, l, m, r);? After r gets smaller due to the recursion, eventually r=0, the condition l
So it's taken a few days and attempts to wrap my head around the implementation of this algorithm. The only part I'm now confused on is: At merge_sort_recursion but before merge_sorted_arrays, you claim that the sub-arrays are sorted. How??? We only divided arrays into smaller and smaller arrays but never sorted them
Edit: Like lines 66 and 67 in your Github code, you claim "at this point both portions of the array have been sorted, and we now merge the sorted portions of the array" I don't see a code preceding this line that "sorts" the array. Only divides it into smaller and smaller parts
It's the two previous calls to merge_sort_recursion that sort those portions of the array, and the call to merge_sort_recursion in which this is taking place will return the new combined portion of the array (also sorted). When merge_sort_recursion() 'returns/stops' after a call to merge_sorted_arrays(), the portion of the array between l...r will be sorted. So when we have two previous calls to merge_sort_recursion() *in* merge_sort_recursion(), those two portions will be sorted as well. When merge_sort_recursion keeps calling itself with smaller and smaller portions of the array, eventually we get down to portions of a single element in the array. At that point we'll have a call to merge_sorted_arrays() and those two elements get merged into a portion of two elements. But that call to merge_sorted_arrays() is itself the last thing that will occur in a call to merge_sort_recursion(), and so that call to merge_sort_recursion() will "return/stop". Now that call to merge_sort_recursion occurred *inside* of another call to merge_sort_recursion(), and so *that* "parent call" of merge_sort_recursion() will now have a sorted portion of the array due to this "child call" that it made that has now "returned/stopped". Merge sort is honestly a really tough one to think about, hopefully this helped somewhat. :-)
Hey there!
It was a great video.
Can you please launch full DSA course (trees and graphs etc.)!
Thanks Lakshay! :-) I don't have a full DSA course but I do have a Udemy course on Linked Lists in C: portfoliocourses.com/.
But it shows error (must have constant value expression) when I tried to create temporary array
There are different versions of the C language that have been made over the years. In C99, a version that was defined in 1999, you can declare an array like we do in this video using a variable for the array length. In older versions of C like C89, you cannot. So you could use a newer C99 compiler. At this point C99 has been out for many years so it is not unusual to write code that uses the capabilities of C99. That said, another way to solve the problem would be to use dynamic memory allocation: ua-cam.com/video/R0qIYWo8igs/v-deo.html. You could use malloc or calloc to allocate space for the temp array, and then free the space when you are done with it, and that would work fine too. :-)
why "k = l" in the function merge_sorted_arrays, what if I chang it to "k = 0" .
Helpp me plz
There is more comments explaining things here that you may find helpful: github.com/portfoliocourses/c-example-code/blob/main/merge_sort.c. We set k to l because it is going to be used to move through the elements from l .... r, i.e. the portion of the array that the two sorted portions are being merged into. :-)
good job
How is temp left and temp right in sorted form?
Can u use an example where they r not sorted
Great question! :-) Check out the comment at the bottom of the source code file here, where there is a visualization of how merge sort works: github.com/portfoliocourses/c-example-code/blob/main/merge_sort.c. When the "merging" starts, the left and right temp arrays are only a single element in length, and are so sorted by default (an array of one element is always sorted). They are then sorted into arrays of length 2 and so on from there as they are merged together, so a temp left and temp right array both of length 1 are merged to produce a sorted "array" of length 2. And so on from there. :-)
Excuse me sir..
i'm still confusing to know about the recursion part..
what is the value when we call function merge_sort_recursion(a, l, m) and merge_sort_recursion(a, m + 1, r) ?
because, when l doesn;t greater than r recursion continuesly running.
and what is the value that we are passing into function merge_sorted_arrays(a, l, m, r)
i got little confused because when i try to print the value of l, m and r, the compiler return value like this..
l = 0 | m = 0 | r = 1
l = 0 | m = 1 | r = 2
l = 3 | m = 3 | r = 4
l = 0 | m = 2 | r = 4
l = 5 | m = 5 | r = 6
l = 5 | m = 6 | r = 7
l = 8 | m = 8 | r = 9
l = 5 | m = 7 | r = 9
l = 0 | m = 4 | r = 9
thank you...
When we call merge_sort_recursion in those ways, we're applying merge sort to the "left" and "right" portions of the array, split at the midpoint. When we call merge_sorted_arrays we're passing the indexes of the left portion (l...m) and right portion (m+1...r). The comments in the code here might help out a bit more too: github.com/portfoliocourses/c-example-code/blob/main/merge_sort.c. :-)
this is the easiest merge sort code 🤯🤯🤯
Hello I am back 😃 I have a question, in your github code (line 15, 16 and 17) you write void function_name(something); and end with a semicolon. What are these lines used for? I have always just made my function like this:
void function_name(something)
{
//do something
}
Welcome back! :-) And great question, those are what are called function declarations. They allow us to keep our main function at the top of the file rather than burying it underneath a bunch of function definitions. The idea is covered in this video here: ua-cam.com/video/NGQoKF2Ggt8/v-deo.html.
@@PortfolioCourses Thank you, have a great weekend! :)
You’re welcome, and you too! :-)
Thanks!
You're very welcome Addison! And thank you so much for the super thanks, that's very generous of you. 🙂
thanks for your explanation, I do this program well, but ......when running the program gives me a " segmentation fault " and does not give the arranged elements, could you tell me why, thanks ...
Hmm, I would not be able to tell for sure without looking at your code. The code in this video is posted here and it will work correctly: github.com/portfoliocourses/c-example-code/blob/main/merge_sort.c. You could compare your code against this code to see if there are any differences that could cause this issue.
@@PortfolioCourses
#include
void merg_sort(int arry[],int len);
void merg_sort_recursion(int arry[],int l, int r); //l :left portion , r :reight
void merg_sorted_arry(int arry[],int l,int m, int r); //l :left portion , r :reight , m :middel of arry.
int main()
{
int arry[] = {9 , 5, 7, 8, 1, 0, 6, 3, 4, 2};
int len = sizeof(arry) / sizeof(arry[0]);
// printf("number of element : %i
",len);
merg_sort(arry , len); // array actualy sorted.
for (int i=0 ; i < len ; i++)
printf("%d ",arry[i]);
printf("
");
return 0;
}
void merg_sort(int arry[],int len)
{
merg_sort_recursion(arry , 0 , len-1);
// 0 = index left side, (len-1 )= index right side
}
void merg_sort_recursion(int arry[] , int l , int r) // where r=len-1
{
if (l < r)
{
int m = l + (r-1) / 2; // middel index of arry.
merg_sort_recursion(arry ,l , m); //sorted index left side
merg_sort_recursion(arry, m+1 , r); //soorted index right side
merg_sorted_arry(arry,l,m,r);
}
}
void merg_sorted_arry(int arry[] ,int l ,int m , int r)
{
int left_length = m - l + 1;
int right_length = r-m ;
int temp_left[left_length];
int temp_right[right_length];
for (int i=0 ; i< left_length ; i++)
temp_left[i]=arry[l+i];
for (int i=0 ; i< right_length ; i++)
temp_right[i]=arry[m+1+i];
int i , j ,k ;
for (i=0 , j=0, k=l ; k= right_length || temp_left[i]
@@PortfolioCourses I actually compare between two code it is the same but when i compiler the program give me "segmentation fault " and when compiler your program it is work fine
@@hmgr5977 There must be at least one difference in the code then, maybe several differences. For example this line here has an error:
int m = l + (r-1) / 2; // middel index of arry.
It should be (r - l), not (r - 1).
@@PortfolioCourses yes. this was the error, the problem solved, thanks
when you initialize the temp array is it sorted? i think it is unsorted then you sorted all to the original array which is a[]
The arrays temp_left and temp_right are sorted when they are initialized, yes. And then we merge them into 'a' in a sorted order.
what? In my understanding, temp_left and temp_right are unsorted then when the for loop gets executed containing the initializers i=0, j=0, k=l. In my undertanding, i dont see how you sorted the both values on temp_left and temp_right.
or perhaps i didn't see the logical of how you sort both the temp_left and temp_right
@@franciscrypto9143 It works using recursion. We keep splitting up the array into smaller and smaller chunks with the merge_sort_recursion() function until we're left with the temp_left and temp_right being made up of "arrays" of a single element, which are by definition both 'sorted'. We then start merging them into larger sorted arrays (the "merge" part of merge sort) using the merge_sorted_arrays() function. So that's why temp_left and temp_right are sorted.
The visualization at the bottom of this code shows what's going on: github.com/portfoliocourses/c-example-code/blob/main/merge_sort.c.
// [38, 27, 43, 3, 9, 82, 10]
// / \
// [38, 27, 43, 3] [9, 82, 10]
// / | | \
// [38, 27] [43, 3] [9, 82] [10]
// / | / | / \ |
// [38] [27] [43] [3] [9] [82] [10]
// \ / \ / \ / |
// [27, 38] [3, 43] [9, 82] [10]
// \ / \ /
// [3, 27, 38, 43] [9, 10, 82]
// \ /
// [3, 9, 10, 27, 38, 43, 82]
//
The first 4 rows are the "splitting" part of the algorithm, splitting the array into smaller and smaller pieces. The last 4 rows show the "merging" happening. So for example, in the 4th row down, [38] would be temp_left and [27] would be temp_right, and they are both "sorted" at this point (because arrays of one element are by definition sorted). They get merged into the sorted array [27,38]. At the same time, in another call to merge_sorted_arrays [43] and [3] were merged into [3,43]. And then if you look at the 5h row we now have a sorted temp_left array [27,38] and a sorted temp_right array [3,43] that get sorted into [3,27,38,43].
why when we compute left_length we add 1, but not when we compute right_length?
Great question! It's essentially because we want the left portion to go from 0...m and we want the right portion to go from m+1....r.
If have an array with let's say 8 elements, we have indexes 0,1,2,3,4,5,6,7. So merge_sort_recursion will be called with l = 0 and r = 7 because length-1 = 7. Then the middle will be 0 + (7 - 0) / 2 = 3 (due to integer division). So then merge_sorted_arrays will be called with l = 0, r = 7, m = 3. And if we want the left portion be the indexes 0,1,2,3 and the right portion to be the indexes 4,5,6,7, so that it's an even split, then when we calculate the left_length we have m - l + 1 to make sure we get 4 and not 3.
Notice we have + 1 when copying the right portion of the array:
for (int i = 0; i < right_length; i++)
temp_right[i] = a[m + 1 + i];
That's for a similar reason, it's because we want the right portion to start at m + 1. :-)
As someone who is new to coding, would experienced professionals consider this type of stuff quite difficult? Because if this is normal or easy work, I don't think I'm cut out for algorithms lol
From what I've seen, this is looking at things pretty abstractly. There are libraries that implement these things without you having to do all the steps. It's just important to know how this works when you start talking time complexity.
i understand the algorithm but how does the 'r' changes to sort the right half of the left half of the left half and so on, i don't get it can you explain please, in my understanding 'r' remains 9 in your video every time we call it.
That's a great question! :-) r changes right here:
// find the midpoint of l and r
int m = l + (r - l) / 2;
// apply the function recursively to the left and right portions split
// at the midpoint
merge_sort_recursion(a, l, m);
We calculate 'm' as the midpoint, but then notice how we pass m to merge_sort_recursion as "the new r". So for this function call to merge_sort_recursion, r will not be 9, r will be the midway point between the last function call's l and r values. :-)
@@PortfolioCourses Hmmm now i see, thank you so much for the explanation, amazing video btw, keep it going. ;)
damnn this is a great video great job
Thank you, glad to hear you enjoyed it! :-D
Thank you. It was useful but in C89 this solution doesnt work.
Thank you
You’re welcome! :-)
Very nice
Thank you very much again! :-D
In merge_sort_recursion, why is m = l + (r - l) / 2 ??? Why not r /2 ??
This video explains why we calculate the middle index like that instead of (l + r) / 2, but basically it has to do with prevent an integer overflow bug: ua-cam.com/video/JNFGvjATOUA/v-deo.html. :-)
@@PortfolioCourses I'm so happy that you reply to comments even today T_T Thank you! You're the guiding light for so many of us who are stuck with our journies
@@qneqne8440 You're welcome! 🙂
what font is that?
I think it's called "Menlo". :-)
I hope you next video is about how to display the passing in merge sort
I’m not sure what you mean by display the passing, do you mean display which values are in each sub array? Or do you mean display the tree of merges?
@@PortfolioCourses like that
I previously is looking at a similar merge sort algorithm and confused. Thank you for reminding me that we are actually merging two SORTED array...
You're welcome Wen Mia! 😀
which IDE you used ? name please
xcode
@@bryanmelvin3458 its Xcode probably as the interface I know
Yeah agreed
for some reason i really do not like and having a hard time comprehending the for loop that contains i j k as indices at the same time. So instead I prefer while loop.
It’s definitely a subjective thing, beautiful code is sometimes in the eye of the beholder! :-)
@@PortfolioCourses Thank you so much programming sensei
G.O.A.T.
No further comment required.
i couldn't get it at all :(
Merge sort is a really tough sorting algorithm to understand. 🙂 It's really important that you understand a lot of the background knowledge required first too, like recursion, arrays, passing arrays to functions, etc. These videos might help a bit:
Recursion: ua-cam.com/video/STWnc6ZY2fw/v-deo.html
Array Basics: ua-cam.com/video/SqOphaInWOs/v-deo.html
Passing Arrays To A Function: ua-cam.com/video/oe2bZKjiWrg/v-deo.html
Merge sort is also a 'divide and conquer algorithm', so learning more about how these algorithms work may also be helpful: en.wikipedia.org/wiki/Divide-and-conquer_algorithm
Quicksort is another divide and conquer algorithm that is pretty tricky, but it might be a bit easier to understand than merge sort at first: ua-cam.com/video/0jDiBM68NGU/v-deo.html
Great explanation but this unfortunately is the type of thing that makes me question if I can be a great developer
Thanks you... I will say that merge sort is a pretty tricky to understand algorithm, so if you find it very difficult to understand, that's very normal. Also, most developers will never need to write algorithms like quicksort, most developers write code that is less about 'algorithms' and more about 'working with a database'. So this isn't representative of the type of work that developers do. So I wouldn't recommend being discouraged. :-)
It shows "Segmentation fault (core dumped)" when compiling. How can i solve this problem?
Btw thanks, your video helps a lot. I can totally understand as a beginner.😆
You're welcome! :-) The code for the video is available here: github.com/portfoliocourses/c-example-code/blob/main/merge_sort.c. It should not cause a compilation error to occur. Can you perhaps copy and paste the code you are trying to compile into a comment? Maybe myself or someone else can spot the issue. :-)
@@PortfolioCourses Oops, got it. Tiny mistakes, much appreciate for the quick response!!
@@chanhugo6228 No problem, glad to hear you got it sorted out! 😀
You should be a voice actor lol
Lol, thank you! :-)
Looks like space complexity = O(nlogn). You can do better by avoiding temp arrays which will give you O=(n). en.wikipedia.org/wiki/Merge_sort