For me, merge sort is quite complex. It requires dividing the list to be sorted in smaller parts and then merging them. It works on divide and conquer philosophy.
For example, let us consider an array of 10 elments:
int array[] = {2,3,1,4,5,4,2,3,12,10};
In divide section, you will divide in such a way that in every divided part, there are only one element:
void divide(int array[],int l,int r)
{
if ( l != r )
{
int mid = ( l + r ) / 2;
divide(array,l,mid);
divide(array,mid+1,r);
merge(array,l,r);
}
}
We start dividing it by middle element.
Now, we will merge them:
void merge(int array[],int l,int r)
{
int A[10];
int B[10];
int mid = ( l + r ) / 2;
int j = 0;
int i;
for (i = l; i <= mid; ++i)
{
A[j++] = array[i];
}
j = 0;
for (i = mid + 1; i <= r; ++i)
{
B[j++] = array[i];
}
int k = l;
for (i = 0,j=0; i <= mid - l && j <= r - mid -1;)
{
if ( A[i] < B[j])
{
array[k++] = A[i];
i++;
}
else
{
array[k++] = B[j];
j++;
}
}
while ( i <= mid - l )
{
array[k++] = A[i];
i++;
}
while ( j <= r - mid -1 )
{
array[k++] = B[j];
j++;
}
}
Merging is quite complex. First we copy half of the elements in array A and another half in array B.
int j = 0;
int i;
for (i = l; i <= mid; ++i)
{
A[j++] = array[i];
}
j = 0;
for (i = mid + 1; i <= r; ++i)
{
B[j++] = array[i];
}
Then we start comparing elements from array A and B, and placing them to the array accordingly:
for (i = 0,j=0; i <= mid - l && j <= r - mid -1;)
{
if ( A[i] < B[j])
{
array[k++] = A[i];
i++;
}
else
{
array[k++] = B[j];
j++;
}
}
Now, there might be a situation where some elements are left in array A or array B. That needs to be taken care of:
while ( i <= mid - l )
{
array[k++] = A[i];
i++;
}
while ( j <= r - mid -1 )
{
array[k++] = B[j];
j++;
}
This will copy whole array.
A working example is:
#include <stdio.h>
void merge(int array[],int l,int r)
{
int A[10];
int B[10];
int mid = ( l + r ) / 2;
int j = 0;
int i;
for (i = l; i <= mid; ++i)
{
A[j++] = array[i];
}
j = 0;
for (i = mid + 1; i <= r; ++i)
{
B[j++] = array[i];
}
int k = l;
for (i = 0,j=0; i <= mid - l && j <= r - mid -1;)
{
if ( A[i] < B[j])
{
array[k++] = A[i];
i++;
}
else
{
array[k++] = B[j];
j++;
}
}
while ( i <= mid - l )
{
array[k++] = A[i];
i++;
}
while ( j <= r - mid -1 )
{
array[k++] = B[j];
j++;
}
}
void divide(int array[],int l,int r)
{
if ( l != r )
{
int mid = ( l + r ) / 2;
divide(array,l,mid);
divide(array,mid+1,r);
merge(array,l,r);
}
}
int main(int argc, char const *argv[])
{
int array[] = {2,3,1,4,5,4,2,3,12,10};
int n = 10;
divide(array,0,n-1);
for (int i = 0; i < n; ++i)
{
printf("%d\n", array[i]);
}
return 0;
}
The time complexity of merge sort is O(nlogn). Also, it requires O(n) space to save temporary array elements.
But, you may ask why should we use merge sort over quicksort, here are the reasons:
1. Merge sort is stable algorithm, while quicksort isn't. It means for equal values, the position doesn't change.
2. Merge sort worst case in O(nlogn). While that of for quicksort is O(n*n).
Comments
Post a Comment