In | Merge In Place in C ++ ; Both sorted sub - arrays must be adjacent in ' a ' ' an ' is the length of the first sorted section in ' a ' ' bn ' is the length of the second sorted section in ' a ' ; Return right now if we 're done ; Do insertion sort to merge if size of sub - arrays are small enough ; p -- ) Insert Sort A into B ; p ++ ) Insert Sort B into A ; Find the pivot points . Basically this is just finding the point in ' a ' where we can swap in the first part of ' b ' such that after the swap the last element in ' a ' will be less than or equal to the least element in ' b ' ; Swap first part of b with last part of a ; Now merge the two sub - array pairings ; } merge_array_inplace ; Merge Sort Implementation ; Sort first and second halves ; Now merge the two sorted sub - arrays together ; Function to print an array ; Driver program to test sort utility
#include <iostream> NEW_LINE using namespace std ; #define __INSERT_THRESH  5 NEW_LINE #define __swap ( x , y )  (t = *(x), *(x) = *(y), *(y) = t) NEW_LINE static void merge ( int * a , size_t an , size_t bn ) { int * b = a + an , * e = b + bn , * s , t ; if ( an == 0 || bn == 0 || ! ( * b < * ( b - 1 ) ) ) return ; if ( an < __INSERT_THRESH && an <= bn ) { for ( int * p = b , * v ; p > a ; for ( v = p , s = p - 1 ; v < e && * v < * s ; s = v , v ++ ) __swap ( s , v ) ; return ; } if ( bn < __INSERT_THRESH ) { for ( int * p = b , * v ; p < e ; for ( s = p , v = p - 1 ; s > a && * s < * v ; s = v , v -- ) __swap ( s , v ) ; return ; } int * pa = a , * pb = b ; for ( s = a ; s < b && pb < e ; s ++ ) if ( * pb < * pa ) pb ++ ; else pa ++ ; pa += b - s ; for ( int * la = pa , * fb = b ; la < b ; la ++ , fb ++ ) __swap ( la , fb ) ; merge ( a , pa - a , pb - b ) ; merge ( b , pb - b , e - pb ) ; #undef __swap #undef __INSERT_THRESH void merge_sort ( int * a , size_t n ) { size_t m = ( n + 1 ) / 2 ; if ( m > 1 ) merge_sort ( a , m ) ; if ( n - m > 1 ) merge_sort ( a + m , n - m ) ; merge ( a , m , n - m ) ; } void print_array ( int a [ ] , size_t n ) { if ( n > 0 ) { cout << " ▁ " << a [ 0 ] ; for ( size_t i = 1 ; i < n ; i ++ ) cout << " ▁ " << a [ i ] ; } cout << " STRNEWLINE " ; } int main ( ) { int a [ ] = { 3 , 16 , 5 , 14 , 8 , 10 , 7 , 15 , 1 , 13 , 4 , 9 , 12 , 11 , 6 , 2 } ; size_t n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; merge_sort ( a , n ) ; print_array ( a , n ) ; return 0 ; }