Implementing Merge Sort Algorithm in C/C++

Below function implements the Merge Sort algorithm. The function takes input as a array of integers start and end position of the array. Merge Sort  uses the Divide and Conquer method for sorting the array. 

MergeSort method divides the array and Merge method merges sorted array in sorted fashion.

void MergeSort( int * intArray, int start, int end) { if( start < end ) { int mid = (end + start)/2; Sort( intArray, start, mid ); Sort( intArray, mid+1, end ); Merge( intArray, start, mid, end); } } void Merge( int * intArray, int start, int mid, int end) {     int mid2 = mid +1;     int nFirst = (mid - start)  + 1;     int nSec= (end - mid);     int * pLeft = new int [nFirst + 1];         int * pRight = new int [nSec + 1];          for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)     {         pLeft[cntr1] = intArray[start + cntr1];     }         pLeft[nFirst] = intArray[mid] + intArray[end];          for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)     {         pRight[cntr1] = intArray[mid2 + cntr1];     }     pRight[nSec] = intArray[mid] + intArray[end];          for( int cntr = start, j = 0, k = 0; cntr <= end ; )     {         if( pLeft[j] < pRight[k] )         {             intArray[cntr++] = pLeft[j++];             continue;         }                 intArray[cntr++] = pRight[k++];     }     delete [] pLeft;     delete [] pRight; }

Merge method can write such as stop once either array left or right has had all its elements copied back to intArray then copy the reminder other array back to intArray as given below.

void Merge( int * intArray, int start, int mid, int end) {     int mid2 = mid +1;     int nFirst = (mid - start)  + 1;     int nSec= (end - mid);     int *pLeft = new int [nFirst];       int *pRight = new int [nSec];        for ( int cntr1= 0; cntr1 < nFirst ; ++ cntr1)     {         pLeft[cntr1] = intArray[start + cntr1];     }            for ( int cntr1 = 0; cntr1 < nSec ; ++ cntr1)     {         pRight[cntr1] = intArray[mid2 + cntr1];     }     int cntr = start, j = 0, k = 0;     for( ; j < nFirst && k < nSec ; )     {         if( pLeft[j] < pRight[k] )         {             intArray[cntr++] = pLeft[j++];         }                else         {             intArray[cntr++] = pRight[k++];         }     }     for( ; j < nFirst ; j++)     {         intArray[cntr++] = pLeft[j];     }     for( ; k < nSec ; k++)     {         intArray[cntr++] = pRight[k];     }     delete [] pLeft;     delete [] pRight; }

You can even use insertion sort to sort and merge the array as shown below. 

void Merge( int * intArray, int start, int mid, int end) {     for( int nCtr = mid+1; nCtr <= end; nCtr++)     {         int n = nCtr - 1;         int key = intArray[nCtr];         while( n >= start && intArray[n] > key  )         {             intArray[n+1] = intArray[n];             n--;         }         intArray[n+1] = key;     } }