Thursday, July 29, 2010

ASP.Net - Merge Sort

Merge Sort


The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list.


Elementary implementations of the merge sort make use of three arrays - one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don't yield any significant performance enhancement over the recursive algorithm on most machines.


The merge sort is slightly faster than the Heap Sort for larger sets, but it requires twice the memory of the Heap Sort because of the second array. This additional memory requirement makes it unattractive for most purposes - the Quick Sort is a better choice most of the time and the Heap Sort is a better choice for very large sets.


Like the Quick Sort, the merge sort is recursive which can make it a bad choice for applications that run on machines with limited memory.






Merge Sort Routine Code


// array of integers to hold values
private int[] a = new int[100];
private int[] b = new int[100];

// number of elements in array
private int x;

// Merge Sort Algorithm
public void sortArray()
{
m_sort( 0, x-1 );
}

public void m_sort( int left, int right )
{
int mid;

if( right > left )
{
mid = ( right + left ) / 2;
m_sort( left, mid );
m_sort( mid+1, right );

merge( left, mid+1, right );
}
}

public void merge( int left, int mid, int right )
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while( (left <= left_end) && (mid <= right) )
{
if( a[left] <= a[mid] )
{
b[tmp_pos] = a[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
b[tmp_pos] = a[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while( left <= left_end )
{
b[tmp_pos] = a[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}

while( mid <= right )
{
b[tmp_pos] = a[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for( i = 0; i < num_elements; i++ )
{
a[right] = b[right];
right = right - 1;
}
}

No comments:

Post a Comment