#include <iostream>

using namespace std ;

void  swap( int &a , int &b ) {
      int n = a ;
      a = b ;
      b = n ;
}
 
void  merge( int *a , int s1 , int s2 ) {

    int  s = s1 + s2 ;
    int  *b = new int[s] ;
    
    int i , j ;
    
    i = 0 ; j = s1 ;
    for ( int n = 0 ; n < s ; ++n ) {
        if ( i == s1 ) {
           b[n] = a[j++] ;
        } else if ( j == s ) {
           b[n] = a[i++] ;
        } else {
           b[n] = ( a[i] < a[j] ? a[i++] : a[j++] ) ;
        }   
    } 

    for ( i = 0 ; i < s ; ++i ) a[i] = b[i] ; 
    delete [] b ;  
}


void  merge_sort( int *a , int s ) {
      if ( s == 2 && a[0] > a[1] ) {
           swap(a[0],a[1]) ;
      } else if ( s > 2 ) {
           int  first_half = s/2 ;
           int  second_half = s - first_half ;  
           merge_sort( a , first_half ) ;
           merge_sort( a+first_half , second_half ) ;
           merge( a , first_half , second_half ) ;     
      }      
}
 
int main() {
    
    const int S = 9 ;
    int no[S] = { 3 , 1 , 5 , 2 , 8 , 2 , 4 , 7 , 6} ;

    merge_sort( no , S ) ;
    for ( int i = 0 ; i < S ; ++i ) cout << no[i] << " " ;
    cout << endl ;
    
    return 0 ;
}