algorithm Merge Sort Merge Sort Implementation in C & C#
Example
C Merge Sort
int merge(int arr[],int l,int m,int h)
{
int arr1[10],arr2[10]; // Two temporary arrays to
hold the two arrays to be merged
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0; i<n1; i++)
arr1[i]=arr[l+i];
for(j=0; j<n2; j++)
arr2[j]=arr[m+j+1];
arr1[i]=9999; // To mark the end of each temporary array
arr2[j]=9999;
i=0;
j=0;
for(k=l; k<=h; k++) { //process of combining two sorted arrays
if(arr1[i]<=arr2[j])
arr[k]=arr1[i++];
else
arr[k]=arr2[j++];
}
return 0;
}
int merge_sort(int arr[],int low,int high)
{
int mid;
if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
// Combine
merge(arr,low,mid,high);
}
return 0;
}
C# Merge Sort
public class MergeSort
{
static void Merge(int[] input, int l, int m, int r)
{
int i, j;
var n1 = m - l + 1;
var n2 = r - m;
var left = new int[n1];
var right = new int[n2];
for (i = 0; i < n1; i++)
{
left[i] = input[l + i];
}
for (j = 0; j < n2; j++)
{
right[j] = input[m + j + 1];
}
i = 0;
j = 0;
var k = l;
while (i < n1 && j < n2)
{
if (left[i] <= right[j])
{
input[k] = left[i];
i++;
}
else
{
input[k] = right[j];
j++;
}
k++;
}
while (i < n1)
{
input[k] = left[i];
i++;
k++;
}
while (j < n2)
{
input[k] = right[j];
j++;
k++;
}
}
static void SortMerge(int[] input, int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
SortMerge(input, l, m);
SortMerge(input, m + 1, r);
Merge(input, l, m, r);
}
}
public static int[] Main(int[] input)
{
SortMerge(input, 0, input.Length - 1);
return input;
}
}
