MergeSort -O(nlogn) in the worst case!!
Mergesort is a well-known sorting algorithm ,which has O(nlogn) complexity in the worst case! ...
it belongs to DIVIDE and CONQUER paradigm!
INPUT
an integer array a [ ] with 'n' elements.
OUTPUT
array a[ ] containing same data as input such that
a[0]<=a[1]<=a[2]<=...............a[n-2]<=a[n-1]
The algorithm can be divided into 3 parts :
example showing the implementation of Mergesort from Wikipedia
Here the second step revelas that we are going solve our task RECURSIVELY!well ! we know that every recursive function will have some Terminating condition ! what about that condition in this case!
Here the Terminating condition is...
An array of size 1 is always sorted !
PSEUDO CODE
the algorithm mergesort contains two functions...
1)MERGESORT(A,begin,end) :
The procedure MERGESORT(A,begin,end) sorts the elements in the subarray A[begin. . .end]. If begin>=end , the subarray has at most one element therefore already sorted. Otherwise, the divide step simply computes an index 'middle' that divides A[begin. .end] into two subarrays: A[begin. .middle], containing ceil(n/2) elements, and A[middle + 1. .end], containing floor (n/2) elements..
Here is the Pseudocode for the method MERGESORT(A,begin,end)
2) MERGE(A,begin,middle,end) : The method MERGE(A,begin,middle,end) merges two already sorted sub-arrays to sorted array! the pseudo code is..
SOURCE CODE :
HERE is my Well commented C++ code for Merge sort !
PROOF FOR COMPLEXITY :
the O(nlogn) complexity of mergesort in worstcase can be proved by solving following Recurrence relation...
T(N)=2*T(N/2)+ N for N>1 Assume T(1)=0 ans N is a power of two.
Proof:
T(N)/N=2* T(N/2)/N + 1
T(N)/N = T(N/2) / (N/2) + 1
T(N)/N= T(N/4) / (N/4) + 1 +1 // Here we will get 2 '1' s
.
.
.
.
T(N)/N=T(N/N)/(N/N) +1+1+...................+1 //Here we will get 'K' 1's where 2^K=N.
T(N)/N=T(1)+K
we know T(1)=0
So,
T(N)/N=K
T(N)/N=log(N) as 2^K=N
which implies
T(N)=N logN
This finally proves that the complexity of mergsort is O(N logN)
PLUS points:
The best complexity that can be achieved using any comparision-based sorting algorithm is
O(n logn)
Merge sort achieves this even in the worst case !
MINUS points :
it really uses TOO MUCH ! memory than any other sorting algorithm!
total space required is..
So merge sort uses a total memory of 2N+ logN
while INSERTION and SELECTION SORTS use N+O(1) memory
and QUICK SORT uses N + logN memory..
if you find any BUGS in the post ! please post in the comments! Thank you for reading my Blog :)
Mergesort is a well-known sorting algorithm ,which has O(nlogn) complexity in the worst case! ...
it belongs to DIVIDE and CONQUER paradigm!
INPUT
an integer array a [ ] with 'n' elements.
OUTPUT
array a[ ] containing same data as input such that
a[0]<=a[1]<=a[2]<=...............a[n-2]<=a[n-1]
The algorithm can be divided into 3 parts :
- Divide the array into two equal parts
- Sort each part individually
- Merge the two parts to get sorted output!
example showing the implementation of Mergesort from Wikipedia
Here the second step revelas that we are going solve our task RECURSIVELY!well ! we know that every recursive function will have some Terminating condition ! what about that condition in this case!
Here the Terminating condition is...
An array of size 1 is always sorted !
PSEUDO CODE
the algorithm mergesort contains two functions...
1)MERGESORT(A,begin,end) :
The procedure MERGESORT(A,begin,end) sorts the elements in the subarray A[begin. . .end]. If begin>=end , the subarray has at most one element therefore already sorted. Otherwise, the divide step simply computes an index 'middle' that divides A[begin. .end] into two subarrays: A[begin. .middle], containing ceil(n/2) elements, and A[middle + 1. .end], containing floor (n/2) elements..
Here is the Pseudocode for the method MERGESORT(A,begin,end)
MERGESORT(A,begin,end) { if (begin<end) { middle=ceil( (begin+end)/2) MERGESORT(A,begin,middle); MERGESORT(A,middle + 1, end); MERGE(A,begin,middle,end); } }
2) MERGE(A,begin,middle,end) : The method MERGE(A,begin,middle,end) merges two already sorted sub-arrays to sorted array! the pseudo code is..
MERGE(A,begin,middle,end) { int B[ ]; // extra memory is used to store elements of final array in sorted manner. i=begin; j=middle+1; k=0; while(i<=middle AND j<=end) { if(A[i]<=A[j]) { B[k++]=A[i++]; } else { B[k++]=A[j++]; } } while(i<=middle) { B[k++]=A[i++]; } //in the two while loops only one is executed every time!! while(j<=end) { B[k++]=A[j++]; } k--; while(k>=0) { A[begin+k]=B[k]; //copying elements of B into A } }
SOURCE CODE :
HERE is my Well commented C++ code for Merge sort !
// Mergesort implementation using recursion #include <iostream> using namespace std; void MERGE(int a[],int begin,int middle,int end) { int b[1000]; int i=begin; int j=middle+1; int k=0; while(i<=middle&&j<=end) { if(a[i]<=a[j]) { b[k++]=a[i++]; } else { b[k++]=a[j++]; } } while(i<=middle) { b[k++]=a[i++]; } while(j<=end) { b[k++]=a[j++]; } k--; while(k>=0) { a[begin+k]=b[k]; //copying elements of array b to array a k--; } } void MERGESORT(int a[],int begin,int end) { if(begin<end) { int middle=(begin+end)/2; MERGESORT(a,begin,middle); //sorting first half MERGESORT(a,middle+1,end); //sorting second half MERGE(a,begin,middle,end); } } int main() { int n; cout<<"........MERGE SORT IMPLEMENTATION USING RECURSION.....\n\n"; cout<<"Enter size of Array\n"; cin>>n; int *a=new int[n]; for(int i=0;i<n;i++) cin>>a[i]; MERGESORT(a,0,n-1); cout<<"Elements after sorting using mergesort are\n"; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; }
PROOF FOR COMPLEXITY :
the O(nlogn) complexity of mergesort in worstcase can be proved by solving following Recurrence relation...
T(N)=2*T(N/2)+ N for N>1 Assume T(1)=0 ans N is a power of two.
Proof:
T(N)/N=2* T(N/2)/N + 1
T(N)/N = T(N/2) / (N/2) + 1
T(N)/N= T(N/4) / (N/4) + 1 +1 // Here we will get 2 '1' s
.
.
.
.
T(N)/N=T(N/N)/(N/N) +1+1+...................+1 //Here we will get 'K' 1's where 2^K=N.
T(N)/N=T(1)+K
we know T(1)=0
So,
T(N)/N=K
T(N)/N=log(N) as 2^K=N
which implies
T(N)=N logN
This finally proves that the complexity of mergsort is O(N logN)
PLUS points:
The best complexity that can be achieved using any comparision-based sorting algorithm is
O(n logn)
Merge sort achieves this even in the worst case !
MINUS points :
it really uses TOO MUCH ! memory than any other sorting algorithm!
total space required is..
- for original array - N
- for Auxillary array for merging -N
- extra memory for STACK management during Recursion - logN
So merge sort uses a total memory of 2N+ logN
while INSERTION and SELECTION SORTS use N+O(1) memory
and QUICK SORT uses N + logN memory..
if you find any BUGS in the post ! please post in the comments! Thank you for reading my Blog :)
Please post comments
ReplyDelete