Merge Sort:
Merge sort is a
sorting technique which is based on divide and conquer approach. Given a
sequence of n elements a[1]…a[n], the general idea is to split them into two
sets a[1]…
and
…a[n].
Each set is individually sorted and the resulting sorted sequences are merged
to produce a single sorted sequence of n elements.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgmv3WeYb252Hz-4N6WNd6nFbhMahNqtrgRknyV4fxpfppi2iAMQSGfUcv2APo-vIoZB2JF_VkNZK5ivyBnqUb8ow9zPyv-6PuruvmTvNRpSKCRJ9wF8Zox5OK-c3dlBGqK8h7MFjk5dlEJ/s1600/4.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVnA5O4O9otyLI-B6-gMPFNoRcroZxm0PBQYkFz1vpWg7Rk-yWT8l2Xeimk-vu3y9xtw_7mFSNvqDvXMxfl7uMXhKttZvR61BlWsK_L-boVjjBQNVJyDqiJt0FTXcPBCbnssHECeHW86Be/s1600/5.png)
Algorithm MergeSort(low,high)
{
If(low<high)
{
MergeSort(low,mid)
MergeSort(mid+1,high)
Merge(low,mid,high)
}
}
Merge(low,mid,high)
{
n1=mid-low+1;
n2=high-(mid-1)+1;
let L(1… n1+1)
and R(1… n2+1) be two new arrays
for i=1 to
n1
L[i]=A[low+i-1];
end
for j=1 to
n2
R[j]=A[mid+j];
end
L[n1+1]=
;
![](file:///C:/Users/SANJOY/AppData/Local/Temp/msohtmlclip1/01/clip_image010.png)
R[n2+1]=
;
![](file:///C:/Users/SANJOY/AppData/Local/Temp/msohtmlclip1/01/clip_image010.png)
i=1
j=1
for k=low
to high
if
L[i]≤R[j]
A[k]=L[i]
i=i+1
end
else
A[k]=R[j]
j=j+1
end
end
}
§ Analysis:
If T(n) represents the
total computing time required to perform merge sort on an array of n element,
then the recurrence relation can be represented as:![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDsXv_cw0JIR1CvdcMFgy_7pndXNsdulIQHLdltFV40jD7NlfyMbdG78IyRmJwleiYtFZ0-9XJHWxdQd8rxedj8C_5BBDJPUo0HrQhDn39eNlFhZ4mEGvNr_sXt_2Z8_vnNdazViKk9ydM/s1600/7.png)
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjDsXv_cw0JIR1CvdcMFgy_7pndXNsdulIQHLdltFV40jD7NlfyMbdG78IyRmJwleiYtFZ0-9XJHWxdQd8rxedj8C_5BBDJPUo0HrQhDn39eNlFhZ4mEGvNr_sXt_2Z8_vnNdazViKk9ydM/s1600/7.png)
Hence, we can say that the complexity of merge sort algorithm is
O(nlogn).
No comments:
Post a Comment