#include <iostream>
#include <locale>

using namespace std;

void Merge ( int a[], int left, int mid, int right ) {
	int i, j, k;
	int n1 = mid - left + 1;
	int n2 =  right - mid;

	int L[n1], R[n2];

	for ( i = 0; i < n1; i++ )
	{ L[i] = a[left + i]; }

	for ( j = 0; j < n2; j++ )
	{ R[j] = a[mid + 1 + j]; }

	i = 0;
	j = 0;
	k = left;

	while ( i < n1 && j < n2 ) {
		if ( L[i] <= R[j] ) {
			a[k] = L[i];
			i++;
		}
		else {
			a[k] = R[j];
			j++;
		}

		k++;
	}

	while ( i < n1 ) {
		a[k] = L[i];
		i++;
		k++;
	}

	while ( j < n2 ) {
		a[k] = R[j];
		j++;
		k++;
	}
}

void MergeSort ( int a[], int left, int right ) {
	if ( left < right ) {
		int mid = left + ( right - left ) / 2;

		MergeSort ( a, left, mid );
		MergeSort ( a, mid + 1, right );

		Merge ( a, left, mid, right );
	}
}


int main() {
    setlocale(LC_ALL, "Rus");
	int n;
	cout << "¬ведите размер массива: ";
	cin >> n;
	int a[n];

	for ( int i = 0; i < n; ++i ) {
		cin >> a[i];
	}

	cout << "\n\n»сходный массив: \n";

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

	MergeSort ( a, 0, n - 1 );

	cout << "\n\n—ортированный массив: \n" ;

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

	return 0;
}