#include "stdafx.h"

#include <stdio.h>
#include <tchar.h>
#include <random>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <time.h>

void generuoti(int _N, const char *_file);
void nuskaityti(const char *_file);


void sort_merge();


using namespace std;

double *Data;
double* A;
double* B;
int N;

int main()
{
	srand(time(NULL));
	cout << "generuojame atsitktinius duomenis " << endl;
	generuoti(20, "duom.txt");
	cout << "nuskaitome duomenis " << endl;
	nuskaityti("duom.txt");
	A = new double[N];
	B = new double[N];//jeigu algoritmui reikia papildomo masyvo
	for (int i = 0; i < N; i++) {
		A[i] = Data[i];
	}

	cout << "pradine skaiciu seka:" << endl;
	for (int i = 0; i < N; i++)
		cout << A[i] << " ";
	cout << endl;
	sort_merge();
	cout << "surusiuota skaiciu seka:" << endl;
	for (int i = 0; i < N; i++)
		cout << A[i] << " ";
	cout << endl;

	system("pause");
	return 0;
}

void generuoti(int _N, const char *_file) {
	ofstream os(_file);
	os << _N << endl;
	for (int i = 0; i<_N; i++)
		os << " " << (double)(rand() % 1001) / (double)1000;
	os.close();
}

void nuskaityti(const char *_file) {
	ifstream is(_file);
	if (is.fail()) {
		cout << "failo nera" << endl;
		exit(1);
	}
	is >> N;
	Data = new double[N];
	for (int i = 0; i < N; i++) {
		is >> Data[i];
	}
}


void MergeSort(int l, int r);
void Merge(int l, int m, int r);

void sort_merge() {
	int l = 0;
	int r = N - 1;
	MergeSort(l, r);
}

void MergeSort(int l, int r) {
	if (l<(r))
	{
		int m = (l + r) / 2;
		MergeSort(l, m);
		MergeSort(m + 1, r);
		Merge(l, m, r);
	}

}

void Merge(int low, int mid, int high)
{
	int h, i, j, k;
	h = low;
	i = low;
	j = mid + 1;

	while ((h <= mid) && (j <= high))
	{
		if (A[h] <= A[j])
		{
			B[i] = A[h];
			h++;
		}
		else
		{
			B[i] = A[j];
			j++;
		}
		i++;
	}
	if (h>mid)
	{
		for (k = j;k <= high;k++)
		{
			B[i] = A[k];
			i++;
		}
	}
	else
	{
		for (k = h;k <= mid;k++)
		{
			B[i] = A[k];
			i++;
		}
	}
	for (k = low;k <= high;k++) A[k] = B[k];
}