Hello All ,
In this section i am going to discuss one of the famous sorting technique available for us .
Merge sort :
The main idea behind this sorting is , we first need to divide the set of elements to half , sort on both sides and merge them . This way we are eliminating the need for traversing entire elements .
This technique is a stable sort .
What is a stable sorting ? - In stable sort the implementation or algorithm tries to preserve the order of equal elements , meaning if two objects with equal keys appear in the same order as in the input. I have found this very good example from wiki pages which might clear the things for us .
In this beautiful example , we have two 5s after different type . A stable sort tries to preserve the order in the output .
Now let us come back to merge sort . As mentioned above it divides the elements ,sort & merge as explained in the below figure .
My advise for all the readers is , try to come up with your own logic before looking at the code below . Come back and check my implementations
Coming to finding the complexity of this algorithm , as we have seen in one of the article "Finding complexity " we will use our knowledge to find the complexity here .
As we have seen in the above approach , we would be dividing the set of elements into half for each iteration which gives us the complexity as logn .
Now , for each of the set we sort the elements . So in total there will be n elements that needs to be checked and sorted ( combining all the sets)
So the final complexity of this sorting method would be O(nlogn)
#include
#include
char temp[10]={4,2,10,6,7,9,22,1,8};
void merge_sort(int low, int mid, int high)
{
char local[10];
int i,k ;
int a,b;
a = low;
b = mid+1;
i=low;
while((a <=mid) && (b<=high))
{
if(temp[a]<=temp[b])
{
local[i]=temp[a];
a++;
}
else
{
local[i]=temp[b];
b++;
}
i++;
}
/*For the left over elements during the swap operation ..
* this will be calculated from the position of left & right partitioned values
* */
if(a>mid)
{
for(k=b;k<=high;k++)
{
local[i]=temp[k];
i++;
}
}
else
{
for(k=a;k<=mid;k++)
{
local[i]=temp[k];
i++;
}
}
for(k=low;k<=high;k++)
temp[k] = local[k];
}
void parition(int low , int high)
{
int mid ;
if(low
{
mid = (low+high)/2;
parition(low,mid);
parition(mid+1,high);
merge_sort(low,mid,high);
}
}
void main()
{
int i =0;
parition(0,8);
printf("After sorting the array\n");
for(i=0;i<9 i="" p="">
printf("%d ",temp[i]);
}
Hope i am able to come up with an efficient solution !
