#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

vector<int> n = { 1, 90, 143, 22, 123};



void printArr(vector<int>& arr){
	for(int i = 0; i < arr.size(); i++){
		cout << arr[i] << "\t";

	}
	cout << endl;
}

void merge(vector<int>& arr, int left, int mid, int right){
	vector<int> temp;
	int i = left;
	int j = mid+1;
	
	while(i <= mid && j <= right){
		if(arr[i] <= arr[j]) {
			temp.push_back(arr[i]);
			i++;
		} else {
			temp.push_back(arr[j]);
			j++;
		}
		
	}

	while(j <= right){
		temp.push_back(arr[j]);
		j++;
	}

	while(i <= mid){
		temp.push_back(arr[i]);
		i++;
	}
	
	for(int k = 0; k <temp.size(); k++){
		arr[k+left] = temp[k];
	}

}


void mergeSort(vector<int>& arr, int left, int right){

	if(left >= right) return;
	
	int mid = (left + right) / 2;

	mergeSort(arr, left, mid);
	mergeSort(arr, mid+1, right);
	
	merge(arr, left, mid, right);

}


int bubble(){
//	vector<int> n = { 1, 90, 143, 22, 123};
	printArr(n);

	for(int i = 0; i < n.size()-1; i++){
		for(int j = 0; j < n.size() -i -1; j++){
			if(n[j] > n[j+1]){
				swap(n[j], n[j+1]);
			}
		}
	}
	
	printArr(n);

return 0;
}


int main(){
	printArr(n);
	mergeSort(n, 0, n.size() -1);

	printArr(n);

	return 0;
}