1 Replies - 3139 Views - Last Post: 10 March 2011 - 06:54 AM Rate Topic: -----

#1 light09  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 141
  • Joined: 21-November 09

MergeSort Pseudocode Implemented

Posted 10 March 2011 - 03:49 AM

Hi there, This pseudocode is from the website : http://en.wikipedia.org/wiki/Merge_
I tried to implement it, there were no errors but no output(It was taking way too long(30min))
I just wanted to double check to confirm the root of the cause, the way if it was coded or microprocessor speed.The following is the code:

#include<iostream>
using namespace std;

const int size = 8;

int merge(int L[ ], int R[ ],int y, int z) // y =  length left, z = length right.
{
    int result[size];
    while ( y > 0 || z > 0)
    {
           if( y > 0 && z > 0)
           {
                   if( L[0] <= R[0])
                 {
                              result[0] = L[0];
                              for ( int i = 1; i < size; ++i)
                             {
                                       L[i] = L[i];
                             }
                }
                  else
               {
                         result[0] = R[0];
                        for (int i = 1; i < size; ++i)
                       {
                                R[i] = R[i];
                      }
             }
        }

      else if( y >0)
    {
               result[0] =  L[0];
               for ( int i = 1; i < size; ++i)
                  {
                     L[i] = L[i];
                  }
    }
    else if ( z > 0)
    {
          result[0] = R[0];
                  for (int i = 1; i < size; ++i)
                  {
                     R[i] = R[i];
                  }
    }
}

    return result[size];
}


int merge_sort(int m[ ])
{
    if (size <=1)
    return m[1 ];


    int middle = (size-1)/2;
    int end = size - middle;
    int left[middle],right[end],result[size];
    int x = middle; + 1;

    for( int i = 0; i <=middle; ++i)
    {
        left[i] = m[i];
    }
    for ( int j = 0; j < end; ++j)
    {
        if ( j = 0)
        right[j] = m[middle + 1];
        else
        right[j] = m[j+middle+1];
    }

    left[middle] = merge_sort(left);
    right[size - middle] = merge_sort(right);
    result[size] = merge(left,right,middle + 1,size -middle);
    return result[size];
}

int main()
{
    int array[size] = { 2,4,5,7,1,2,3,6};

    merge_sort(array);

    for ( int i = 0; i < size; ++i)
    cout << "array[" << i << "] = " << array[i] << endl;

    return 0;
}




Thank you for your time.

This post has been edited by light09: 10 March 2011 - 03:52 AM


Is This A Good Question/Topic? 0
  • +

Replies To: MergeSort Pseudocode Implemented

#2 Salem_c  Icon User is online

  • void main'ers are DOOMED
  • member icon

Reputation: 1653
  • View blog
  • Posts: 3,129
  • Joined: 30-May 10

Re: MergeSort Pseudocode Implemented

Posted 10 March 2011 - 06:54 AM

Yes, there is something wrong with your implementation if it's taking 30min to sort 8 numbers.

Here's one thing - running off the end of the array
61	    int left[middle],right[end],result[size];
62	    int x = middle; + 1;
63	 
64	    for( int i = 0; i <=middle; ++i)
65	    {
66	        left[i] = m[i];
67	    }


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1