Merge Sort

# include <iostream>
using namespace std;

int n, arr[100];

int INF = 1<<15;

void merge( int l, int m, int r ) {
    int left[100], right[100], i, j, k;

    for( i=l; i<=m; i++ ) left[i-l]=arr[i];
    left[i-l] = INF;

    for( i=m+1; i<=r; i++ ) right[i-m-1] = arr[i];
    right[i-m-1] = INF;

    i=j=0;
    k=l;
    while( k<=r ) {
        if( left[i]<=right[j] ) arr[k++] = left[i++];
        else arr[k++] = right[j++];
    }
}

void merge_sort( int l, int r ) {
    if( r-l<1 ) return;

    int m = (l+r)>>1;
    merge_sort( l, m );
    merge_sort( m+1, r );
    merge( l, m, r );
}

int main() {
    cin>>n;
    for( int i=0; i<n; i++ ) cin>>arr[i];
    merge_sort( 0, n-1 );

    for( int i=0; i<n; i++ ) cout << arr[i] << " "; cout << endl;
}