Thread: What is the Invariant for iterative mergesort?

  1. #1
    Registered User
    Join Date
    Dec 2003
    Posts
    14

    Unhappy What is the Invariant for iterative mergesort?

    Uhm sorry, newbie question here, but i'm supposed to write an invariant for the below code:
    Code:
    void Mergesort::iterMerge(int array[],int temp[],int lt,int md,int rt)
    {
        int i = lt;
        int j = md+1;
        int k = lt;       
       
       resetResult();
       while(( i <= md )&&( j <= rt ))
    	{
    		comparison++;
    		if( array[ i ] <= array[ j ] )  
          {
    	      temp[ k++ ]= array[ i++ ];
    	      assignment++;
    	   }
          else
          {
    	      temp[ k++ ]= array[ j++ ];
    	      assignment++;
    	   }
    	}
       while( i <= md )
       {
        	temp[ k++ ]= array[ i++ ];
        	assignment++;
       }
    
       while( j <= rt )
       {
         	temp[ k++ ]= array[ j++ ];
         	assignment++;
       }
    }
    
    void Mergesort::mergePass( int array[], int temp[], int current, 
    									int arraySize )
    {
       int count = 0;
    
       while ( count <= arraySize - 2 * current ) 
       {
       		iterMerge( array, temp, count, count+current-1, count+2*current-1 );
          	count = count + 2*current;
       }
       
       if ( count + current < arraySize )
          	iterMerge( array, temp, count, count+current-1, arraySize-1);
       else
       		for ( int i = count; i <= arraySize-1; i++ )
          	{
          		temp[ i ] = array[ i ];   
          		assignment++;
       		}
    }
    
    void Mergesort::iterativeMergesort( DataType* array, int arraySize )
    {
       int current = 1;
       int *temp;
       temp = new int [ arraySize ];
    
       while( current < arraySize )
       {  
       	  mergePass ( array, temp, current, arraySize );
          current += current;                
          mergePass ( temp, array, current, arraySize );
          current += current;                
       } 
    }
    Can anyone please lend me a hint? I'm not quite sure where to start... Thanks in advance
    Last edited by MelaOS; 08-16-2004 at 07:51 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Mergesort in C
    By Oduig in forum C Programming
    Replies: 2
    Last Post: 09-14-2008, 11:30 AM
  2. How do I do MergeSort versus QuickSort instead?
    By dxfist in forum C++ Programming
    Replies: 9
    Last Post: 03-06-2008, 12:12 PM
  3. Natural Mergesort
    By wuzzo87 in forum C Programming
    Replies: 31
    Last Post: 04-14-2007, 09:41 PM
  4. Mergesort
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 10-26-2005, 11:45 PM
  5. Linked Lists + MergeSort....(how?)
    By JoshR in forum C++ Programming
    Replies: 4
    Last Post: 06-03-2005, 02:40 PM