Hello guys, I am trying to write program that will implement merge sort. Before I can do that I obviously need to understand the algorithm, hence this post. I read the tutorial on merge sort and i am not clear on some aspects of the algorithim. So if you could help me out I would appreciate it.
As far as I can tell it works something like this:
1) Read an Array that has an even number of elements
2) Split the array into 2 smaller subarrays
3)Sort the two subarrays
4)and finally merge them back to form the sorted sequence.
So my questions are:
1) Does this algorithm only work for a even number of elements in an array?
2)When it splits the larger array into 2 smaller subarrays, how does it sort the subarrays? It seems like this is where the recursion comes in. I think it constantly divides the subaarrays until you have a bunch of smaller subarrays that have 2 elements, in which case you can easily compare the two elements and work your way back up.
Thats all I need for now, but I am pretty sure I am gonna get stuck when I attempt to code this myself because I am really bad at recursion. If anyone can offer suggestions or any helpful hints I would greatly appreciate it. Thanks for your time.
I am a computer science student, I have studied these sort algorithms but do not remember much. I will answer your question with the experience I have:
1) No, works for any number of elements.
2) You could subdivide until you have only two elements, but you could divide until you have, for example 1/4 of the inital length and then apply another method.
Actually now that I think about it my assignment wants me to compare various sorting algoirithms, so I cant employ any other method into this program because that would kinda of nullify the power of merge sort. Thanks for replying, any other suggestions most welcome :). But i will ask my professor, he told us to google this algorithm anyway hehe.