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
procedure 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)
procedure 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
do
L[i] = A[left +i]
done
5.
for j = 0 to n2-1
do
R[j] =
A[middle+j]
6.
done
7.
k = i = j = 0
8.
while i < n1 & j < n2
do
if L[i]
< R[j]
A[k++]
= L[i++]
else
A[k++]
= R[j++]
9.
done
10.
while i < n1
do
A[k++] = L[i++]
11.
done
12.
while j < n2
do
A[k++] = R[j++]
13.
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++]
7
|
4
|
3
|
0
|
2
|
8
|
6
|
9
|
1
|
5
|
7
|
4
|
3
|
0
|
2
|
8
|
6
|
9
|
1
|
5
|
7
|
4
|
3
|
0
|
2
|
8
|
6
|
9
|
1
|
5
|
4
|
7
|
0
|
3
|
2
|
6
|
8
|
1
|
9
|
5
|
0
|
2
|
3
|
4
|
7
|
1
|
5
|
6
|
8
|
9
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
8
|
9
|
Source
Code
//MergeSort
in Java
import
java.io.*;
public class Merge_Sort
{
int arr[],Size;
void Merge(int top, int n, int m)
{
int c= 0,c1 = 0,c2 = 0,i;
int arr1[]=new int[10];
while((c1 < n)
&& (c2 < m))
{
if(arr[top + c1] < arr[top + n +
c2])
{
arr1[c++] =
arr[top + (c1++)];
}
else
{
arr1[c++] =
arr[top + n + (c2++)];
}
}
while (c1 < n)
{
arr1[c++] = arr[top
+ (c1++)];
}
while (c2 < m)
{
arr1[c++] = arr[top
+ n + (c2++)];
}
for (i = 0; i < n+m;
i++)
{
arr[top + i] = arr1[i];
}
}
void Msort(int top , int n2)
{
int m;
int n;
if(n2 > 1)
{
n = n2 / 2;
m = n2 - n;
Msort(top, n);
Msort(top + n,
m);
Merge(top, n,
m);
}
}
void GetData()throws IOException
{
BufferedReader Br=new
BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter Size :
");
Size=Integer.parseInt(Br.readLine());
arr=new int[Size];
for(int i=0;i<Size;i++)
{
System.out.print("Enter arr["+i+"] : ");
arr[i]=Integer.parseInt(Br.readLine());
}
System.out.print("Original
Values : ");
Disp();
Msort(0, Size);
}
void Disp()
{
for(int i=0;i<Size;i++)
{
System.out.print("
"+arr[i]);
}
}
public static void main(String
args[])throws IOException
{
Merge_Sort MS=new Merge_Sort();
MS.GetData();
System.out.print("\nAfter Sort :
");
MS.Disp();
}
}
Output
Enter Size : 10
Enter arr[0] : 7
Enter arr[1] : 4
Enter arr[2] : 3
Enter arr[3] : 0
Enter arr[4] : 2
Enter arr[5] : 8
Enter arr[6] : 6
Enter arr[7] : 9
Enter arr[8] : 1
Enter arr[9] : 5
Original Values : 7 4 3 0 2 8 6 9 1 5
After Sort : 0 1 2 3 4 5 6 7 8 9
No comments:
Post a Comment