# Thread: What is the Invariant for iterative mergesort?

1. ## 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

Popular pages Recent additions