Monday, November 16, 2009

c# merge sort algorithm implementation

        private int[] MergeSort(int[] a)
{
if ( a.Length == 1)
return a;
int middle = a.Length / 2;
int[] left = new int[middle];
for (int i = 0 ; i < middle ; i ++)
{
left[ i ] = a[ i ];
}
int[] right = new int[a.Length - middle];
for( int i = 0; i < a.Length - middle; i++ )
{
right[i] = a[i+middle];
}
left = MergeSort( left );
right = MergeSort( right );

int leftptr = 0;
int rightptr = 0;

int[] sorted = new int[a.Length];
for(int k = 0 ; k < a.Length; k++)
{
if ( rightptr == right.Length || ((leftptr < left.Length ) && (left[leftptr] <= right[rightptr])))
{
sorted[ k ] = left[ leftptr ];
leftptr++;
}
else if( leftptr == left.Length || ((rightptr < right.Length ) && (right[rightptr] <= left[leftptr] )))
{
sorted[k] = right[rightptr];
rightptr++;
}
}
return sorted;
}

3 comments:

Anonymous said...

Little bit cleaner way to do the actual sort is as follows:

for (int i = 0; i < a.Length; i++)
{
if (l < left.Length && r < right.Length)
{
if (left[l] < right[r]) sorted[i] = left[l++];
else sorted[i] = right[r++];
}
else
{
if (l < left.Length) sorted[i] = left[l++];
else sorted[i] = right[r++];
}
}

Terrell said...

This is great!

navya said...

Great Article
C# Training in Chennai | C# Online Training | ASP.NET Training in Chennai

C# Training in Chennai | Dot Net Training in Chennai | Dot Net Training in Chennai