Thread: Merge sort fails to sort

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    2

    Merge sort fails to sort

    I'm hitting a wall with this. I'm trying to implement merge sort to an existing program. (one that utilizes serveral search algorithms) but I'm unable to get the program to sort correctly. The rest of the program works correctly as i've tested with other sort algorithms.


    Merge sort code
    Code:
    int mergesort (int a[], int p, int r)
    {
            int i;
            int q;
            double x=(p+r)/2;
            if (p<r)
            {
                    q= floor (x);
                    mergesort (a,p,q);
                    mergesort (a,q+1,r);
                    merge(a,p,q,r);
                  cout << "\n";
            }
            return 0;
    }
    
    int merge (int a[], int p, int q, int r)
    {
            int k=p;
            int i=0;
            int l=q-1;
            int t[r];
            while ((p<=l)&&(q<=r))
            {
                    if (a[p]<=a[q])
                    {
                            t[i]=a[p];
                            i++;
                            p++;
                    }
                    else
                    {
                            t[i]=a[q];
                            i++;
                            q++;
                    }
            }
            while (p<=l)
            {
                            t[i]=a[p];
                            i++;
                            p++;
            }
            while (q<=r)
            {
                            t[i]=a[q];
                            i++;
                            q++;
            }
            for (i=k; i<=r; i++)
            {
                    a[i]=t[i-k];
            }
            return 0;
    }
    Here's my current input/ output arrays
    Code:
    Input
    5 8 85 9 78 34 2 6 31 56 7 16 89 476 84 8 22 65 900 76
    output
    5 8 34 2 6 31 56 7 78 16 84 65 76 85 9 89 476 8 22 900
    I can see that it's trying to do some sorting, but it's not fully sorting the data.

    Any help would be appreciated.

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Here's some help.

    Name your variables with meaningful names. a and p and q and k and t and l and r don't get it.

    Comment your code with what your intentions are.
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The ranges that you are merging are not the same as the ranges you have split them into.

    When you split, then the first half is p ... q, and second is q + 1 ... r, but when you merge the first half is p ... q - 1 and the second is q ... r.

    Incidentally, half-open ranges (where the last index is one beyond the range) seem more intuitive and simpler to use. You can compare against <, and not <=. You won't need to add or subtract one, as the ranges would simply be: [p, q) and [q, r).

    Also I don't think you need the double and floor to calculate the middle point, since simple integer division would have the exact same effect.

    And lastly, variable sized arrays are non-standard in C++ (GCC's extension).

    Code:
    int t[r]; //this is not allowed in standard C++
    Name your variables with meaningful names. a and p and q and k and t and l and r don't get it.
    Indeed. Picking letters randomly from the alphabet is not a very good naming strategy. Names like first, last and middle would be a great start.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Sep 2009
    Posts
    2
    It's working perfectly. Thanks for wading through my code to figure out whats wrong. I'll try to remember to use more usefull variable names from now on.

Popular pages Recent additions subscribe to a feed

Similar Threads

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