MergeSort -O(nlogn) in the worst case!!

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 :

1. Divide the array into two equal parts
2. Sort each part individually
3. 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..

1. for original array - N
2. for Auxillary array for merging -N
3. 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 :)