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.