#include "stdafx.h"
#include <omp.h>
#include <iostream>
#include <Windows.h>

void merge(int merged[], int lenD, int L[], int lenL, int R[], int lenR)
{
	int i = 0;
	int j = 0;
#pragma omp parallel shared(i, j)
	{
		while (i < lenL || j < lenR) {
			if (i < lenL & j < lenR) {
				if (L[i] <= R[j]) {
					merged[i + j] = L[i];
					i++;
				}
				else {
					merged[i + j] = R[j];
					j++;
				}
			}
			else if (i < lenL) {
				merged[i + j] = L[i];
				i++;
			}
			else if (j < lenR) {
				merged[i + j] = R[j];
				j++;
			}
		}
	}
}

void mergeSort(int data[], int lenD)
{
	int i = 0;
#pragma omp parallel private(i)
	{
		if (lenD > 1) {
			int middle = lenD / 2;
			int rem = lenD - middle;
			int* L = new int[middle];
			int* R = new int[rem];
			for (i = 0; i < lenD; i++) {
				if (i < middle) {
					L[i] = data[i];
				}
				else {
					R[i - middle] = data[i];
				}
			}
			mergeSort(L, middle);
			mergeSort(R, rem);
			merge(data, lenD, L, middle, R, rem);
		}
	}
}

int main()
{
	int a[10] = { 1,2222,33,333,44444,555555,151217,12132131,55555555555,123456789 };
	int n = 10;

	mergeSort(a, n);

	for (int i = 0; i < 11; i++)
	{
		printf_s("%d\n", a[i]);
	}
	system("PAUSE");

	return 0;
}
