Thread: Merge Sort

  1. #1
    Registered User
    Join Date
    May 2004
    Posts
    215

    Merge Sort

    Im working on this program, and Im trying to implement a merge sort, however, whenever I try it, the code seems to not work. I coded the exact pseudocode from this book I have so I dont know what the problem is.

    Heres where my code is located at:

    http://sourcepost.sytes.net/sourcepo...ource_id=24681

  2. #2
    Registered User
    Join Date
    May 2005
    Posts
    73
    Quote Originally Posted by osal
    Im working on this program, and Im trying to implement a merge sort, however, whenever I try it, the code seems to not work.
    What doesn't work about it? Can you be more specific? Doesn't compile? Gives wrong output? What?

    I'll look at your code, but for future reference you should really post more information.

    P.S. (Is this really code written by you?)

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I coded the exact pseudocode from this book I have
    What book? Who's the author? Books are often wrong when it comes to algorithms. And when the pseudocode is correct, it's very likely that a direct conversion to C or C++ will break because most pseudocode assumes that array indices start with 1.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    May 2004
    Posts
    215
    Yes the code is written by me. This is the pseudocode of the merge sort:
    this is the second function, the recursive function is correct i believe, however this is the pseudocode for the merge function. When I try to sort, it just prints the arrays as -8273439234 or some negative number.


    MERGE(A,p,q,r)
    n1 ← q - p +1
    n2 ← r - q
    create arrays L[1 ..n1 +1] and R[1 ..n2 +1]
    for i ← 1 to n1
    do L[i] ← A[p +i .1]
    for j ← 1 to n2
    do R[ j] ← A[q +j]
    L[n1 +1] ← ∞
    R[n2 +1] ← ∞
    i ←1
    j ←1
    for k ← p to r
    do if L[i] ≤ R[ j]
    then A[k] ← L[i]
    i ← i +1
    else A[k] ← R[ j]
    j ← j +1

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, 02:19 PM
  2. Merge Sort Help
    By blindman858 in forum C++ Programming
    Replies: 5
    Last Post: 05-14-2005, 09:47 PM
  3. Merge Sort
    By blindman858 in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2005, 11:14 AM
  4. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM