Merge sort takes
advantage of the ease of merging already sorted lists into a new sorted list.
It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...)
and swapping them if the first should come after the second. It then merges
each of the resulting lists of two into lists of four, then merges those lists
of four, and so on; until at last two lists are merged into the final sorted
list.
In sorting n
objects, merge sort has an average and worst-case performance of O(n log n). If
the running time of merge sort for a list of length n is T(n), then the
recurrence T(n) = 2T(n/2) + n follows
from the applied algorithm to two lists of half the size of the original list,
and add the n steps taken to merge the resulting two lists.
In the worst case,
the number of comparisons merge sort makes is equal to or slightly smaller than
(n élg nù - 2élg nù +
1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n))
Best
case performance O(n
log n) typical,
O(n)
natural variant
Average
case performance O(n log n)
Worst
case space complexity O(n)
auxiliary
T(n) = 2T(n/2) + cn.
In the same way:
T(n/2) = 2T(n/4) + cn/2, so
T(n) = 4T(n/4) + 2cn.
Going in this way ...
T(n) = 2mT(n/2m) + mcn, and
T(n) = 2kT(n/2k) + kcn = nT(1) + cnlog2n = O(n log n).
In the same way:
T(n/2) = 2T(n/4) + cn/2, so
T(n) = 4T(n/4) + 2cn.
Going in this way ...
T(n) = 2mT(n/2m) + mcn, and
T(n) = 2kT(n/2k) + kcn = nT(1) + cnlog2n = O(n log n).
Merge Sort Algorithm
MergeSort (A, left, right)
1.
if left >= right
2.
return
3.
else
4.
middle
= b(left+right)/2
5.
MergeSort(A,
left, middle)
6.
MergeSort(A,
middle+1, right)
7.
Merge(A,
left, middle, right)
Merge(A, left, middle, right)
Merge(A, left, middle, right)
1.
n1
= middle – left + 1
2.
n2
= right – middle
3.
create array L[n1], R[n2]
4.
for
i = 0 to n1-1
5.
do
6.
L[i]
= A[left +i]
7.
done
8.
for j = 0 to n2-1
9.
do
10.
R[j] = A[middle+j]
11.
done
12.
k
= i = j = 0
13.
while i < n1 & j < n2
14.
do
15.
if L[i] < R[j]
16.
A[k++] = L[i++]
17.
else
18.
A[k++] = R[j++]
1.
done
19.
while
i < n1
20.
do
21.
A[k++]
= L[i++]
22.
done
23.
while
j < n2
24.
do
25.
A[k++]
= R[j++]
26.
done
Merge Sort Pseudo Code
Merge-Sort (A, left,
right)
if left ≥ right return
else
middle ← b(left+right)/2û
Merge-Sort(A,
left, middle)
Merge-Sort(A,
middle+1, right)
Merge(A, left,
middle, right)
Merge(A, left, middle, right)
n1 ← middle
– left + 1
n2 ← right –
middle
create array L[n1],
R[n2]
for i ← 0 to n1-1 do L[i] ← A[left
+i]
for j ← 0 to n2-1 do R[j] ← A[middle+j]
k ← i ← j ← 0
while i < n1
& j < n2
if L[i] < R[j]
A[k++]
← L[i++]
else
A[k++]
←R[j++]
while i < n1
A[k++] ← L[i++]
while j < n2
A[k++] ← R[j++]
Merge Sort – Source Code using Recursive Function
//Merge Sort - Recursive
#include <stdio.h>
#include <conio.h>
int
arr[10];
void merges(int fpos, int n,
int m)
{
int
c= 0,c1 = 0,c2 = 0,i;
int arr1[10];
while ((c1 < n)
&& (c2 < m))
{
if
(arr[fpos + c1] < arr[fpos + n + c2])
{
arr1[c++] = arr[fpos +
(c1++)];
}
else
{
arr1[c++]
= arr[fpos + n + (c2++)];
}
}
while (c1 < n)
{
arr1[c++] =
arr[fpos + (c1++)];
}
while
(c2 < m)
{
arr1[c++]
= arr[fpos + n + (c2++)];
}
for
(i = 0; i < n+m; i++)
{
arr[fpos + i] = arr1[i];
}
}
void
msort(int fpos, int n2)
{
int
n,m;
if
(n2 > 1)
{
n
= n2 / 2;
m
= n2 - n;
msort(fpos,
n);
msort(fpos + n,
m);
merges(fpos, n, m);
}
}
void
main()
{
int i,n;
int
fpos=0;
printf("\n\tEnter
Size [Below 10] : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter [%d]
Element : ",i);
scanf("%d",&arr[i]);
}
printf("\n\tOriginal Values :
");
for (i = 0; i <n; i++)
{
printf("%d",arr[i]);
}
msort(fpos, n);
printf("\n\tAfter
Sort :
");
for (i = 0; i <n; i++)
{
printf("%d
",arr[i]);
}
getch();
}
}
Merge Sort – Source Code using Recursive
Function
//Merge Sort – Non Recursive
#include <stdio.h>
#include <conio.h>
#include <values.h>
// Display the Array
void disp(int ar[],int n)
{
int
i;
for(i=0;i<n;i++)
{
printf("%d
", ar[i]);
}
}
//Merge Function – Sorting and
storing in Auxiliary array then stored back to original
void
merge(int ar[], int Left, int Mid,int Right, int Last)
{
int
L1,L,i,k,m,n,*right,*left;
L=Last
- Right + 1;
right=(int
*)malloc(L*sizeof(int));
L1=
Mid - Left + 1;
left=(int
*)malloc(L1*sizeof(int));
for(i
= 0, k = Right; i < L-1; ++i, ++k)
{
right[i]
= ar[k];
}
for(i
= 0, k = Left; i < L1-1; ++i, ++k)
{
left[i]
= ar[k];
}
right[L-1]
= MAXINT;
left[L1-1]
= MAXINT;
for(k
= Left, m = 0, n = 0; k < Last; ++k)
{
if(left[m]
<= right[n])
{
ar[k]
= left[m];
m++;
}
else
{
ar[k]
= right[n];
n++;
}
}
free(left);
free(right);
}
//Msort Recursive Function for
Dividing
void Msort(int ar[], int n)
{
int s = 1;
int Left, Right;
while(s < n)
{
Left
= 0;
Right
= s;
while(Right
+ s <= n)
{
merge(ar, Left, Left + s, Right, Right + s);
Left = Right + s;
Right = Left + s;
}
if(Right
< n) {
merge(ar, Left, Left + s, Right, n);
}
s
*= 2;
}
}
//Main Function
void
main()
{
int
ar[20],n,i;// = { 1, -2, 2, 4, 3, 6, 5, 8, 7};
clrscr();
printf("\n\tEnter
size Below 20 : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\n\tEnter
Element at [%d] : ",i);
scanf("%d",&ar[i]);
}
printf("\n\tOriginal : ");
disp(ar,n);
Msort(ar,n);
printf("\n\tAfter
Sort : ");
disp(ar,n);
getch();
}
No comments:
Post a Comment