Merge Sort

This is a discussion on Merge Sort within the C++ Programming forums, part of the General Programming Boards category; Hello guys, I am trying to write program that will implement merge sort. Before I can do that I obviously ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    41

    Merge Sort

    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.

  2. #2
    Registered User Mortissus's Avatar
    Join Date
    Dec 2004
    Location
    Brazil, Porto Alegre
    Posts
    152
    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.

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    41
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Sort the best sorting algorithm?
    By sehr alt in forum A Brief History of Cprogramming.com
    Replies: 21
    Last Post: 06-20-2007, 03:19 PM
  2. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 10:47 PM
  3. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 05:03 AM
  4. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM
  5. merge sort
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 09-02-2001, 07:58 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21