MERGE SORT BALANCED MULTIWAY (ĐA LỐI CÂN BẰNG)
#include"time.h"
#include"iostream"
#include"time.h"
#include"algorithm"
#include"fstream"
#include<conio.h>
#include<stdio.h>
using namespace std;
#define TRACE 0
void Swap(int** a, int** b)
{
int* temp = *a;
*a = *b;
*b = temp;
}
void Swap(int&a, int&b)
{
int temp = a;
a = b;
b = temp;
}
void Copy(int source[], int target[], int n)
{
for (int i = 0; i < n; i++) target[i] = source[i];
}
void Print(char name[], int a[], int n)
{
cout << name << ": ";
for (int i = 0; i < n; i++)
if (a[i] != -842150451) cout << a[i] << " ";
cout << endl;
}
int* Read2TextFile(int&n, char* fileName)
{
long start = clock();
/* đọc từng số trong các dòng */
ifstream fin1(fileName);
if (!fin1) // fin1 == NULL
{
cout << "Read2TextFile (n = " << n << ") is KO !!!" << endl;
return NULL;
}
n = count(istreambuf_iterator<char>(fin1), istreambuf_iterator<char>(), '\n');
/* đọc từng dòng, phân phối vào mảng nguyên*/
int* a = new int[n];
ifstream fin2(fileName);
int i = 0;
while (fin2 >> a[i++]);
fin2.close();
long end = clock();
cout << "Read2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
return a;
}
void Write2TextFile(int a[], int n, char* fileName)
{
long start = clock();
ofstream fout(fileName);
for (int i = 0; i < n; i++)
fout << a[i] << endl;
fout.close();
long end = clock();
cout << "Write2TextFile (n = " << n << ") is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
}
int* InitRandom(int&n)
{
cout << "Enter n = "; cin >> n;
int* a = new int[n];
srand((unsigned int)time(0));
for (int i = 0; i < n; i++)
{
//a[i] = rand() % n + 1; // [0:n-1] + 1 = [1:n]
a[i] = ((rand() << 15) | rand()) % n + 1; // [0:n-1] + 1 = [1:n]
}
return a;
}
void Init(int a[], int n)
{
for (int i = 0; i <= n; i++) a[i] = -1;
}
int demduong(int a[], int duong[], int length)
{
int dem = 1, i = 0;
while (i < length - 1)
{
if (a[i] > a[i + 1])
duong[dem++] = i;
i++;
}
duong[dem] = length - 1;
return dem;
}
int ganAvaoB(int a[], int b[], int dau, int cuoi, int vitri)
{
for (int i = dau + 1; i <= cuoi; i++)
b[vitri++] = a[i];
return vitri;
}
int tronAvaoB(int b[], int nb, int duong[], int a[], int i, int n)
{
int *temp = new int[n], ntemp = 0;
Init(temp, n);
int x = 0, y = duong[i - 1] + 1;
while (x <= nb && y <= duong[i])
{
if (a[y] > b[x] && b[x] != -1) temp[ntemp++] = b[x++];
else
{
if (a[y] != -1) temp[ntemp++] = a[y++];
else break;
}
}
while (x <= nb)
{
if (b[x] != -1)
temp[ntemp++] = b[x++];
else break;
}
while (y <= duong[i])
{
if (a[y] != -1)
temp[ntemp++] = a[y++];
else break;
}
ganAvaoB(temp, b, -1, ntemp, 0);
return ntemp;
}
// 2k--------------------------------------------------------------------------------------------------------------
void chay2k(int a1[], int a2[], int b1[], int b2[], int maxlength, int n, int& n1, int& n2, int& nb1, int& nb2,
int duong1[], int duong2[], int& nduong1, int& nduong2)
{
int j = 1;
Init(b1, n); Init(b2, n);
while (j <= maxlength)
{
int *temp = new int[n], ntemp = 0;
Init(temp, n);
if (duong1[j] != -1 || duong2[j] != -1)
{
ntemp = tronAvaoB(temp, ntemp, duong1, a1, j, n);
ntemp = tronAvaoB(temp, ntemp, duong2, a2, j, n);
if (j % 2 == 0) nb2 = ganAvaoB(temp, b2, -1, ntemp, nb2) - 1;
else nb1 = ganAvaoB(temp, b1, -1, ntemp, nb1) - 1;
}
j++;
}
n1 = 0; n2 = 0;
}
void phanphoi2k(int a[], int duong[], int a1[], int a2[], int nduong, int& n1, int& n2, int& nb1, int& nb2)
{
n1 = 0; n2 = 0; nb1 = 0; nb2 = 0;
for (int i = 0; i < nduong; i++)
{
if (i % 2 == 0) n1 = ganAvaoB(a, a1, duong[i], duong[i + 1], n1);
else n2 = ganAvaoB(a, a2, duong[i], duong[i + 1], n2);
}
}
bool stop2k(int a[], int a1[], int a2[], int b1[], int b2[], int duong1[], int duong2[], int& n1, int& n2,
int& nduong1, int& nduong2, int& temp, int& nb1, int& nb2)
{
bool IsRedo = false;
nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2);
if (nduong1 == 1 && nduong2 == 1 && (n1 == 0 || n2 == 0))
{
if (n1 == 0) ganAvaoB(a2, a, -1, n2 - 1, 0);
else ganAvaoB(a1, a, -1, n1 - 1, 0);
return true;
}
else if(nduong1 == 1 && n1 == 0)
{
phanphoi2k(a2, duong2, b1, b2, nduong2, n1, n2, nb1, nb2);
temp = 1;
IsRedo = true;
}
else if(nduong2 == 1 && n2 == 0)
{
phanphoi2k(a1, duong1, b1, b2, nduong1, nb1, nb2, n1, n2);
temp = 1;
IsRedo = true;
}
if (!IsRedo) nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2);
else nduong1 = demduong(b1, duong1, nb1), nduong2 = demduong(b2, duong2, nb2);
return false;
}
void MergeSort2k(int a[], int n)
{
int *a1 = new int[n], *a2 = new int[n], *b1 = new int[n], *b2 = new int[n];
int *duong1 = new int[n], *duong2 = new int[n];
int n1 = 0, n2 = 0, temp = 0, nb1 = 0, nb2 = 0, lan = 0, maxlength = 0;
Init(duong1, n);
int nduong = demduong(a, duong1, n);
phanphoi2k(a, duong1, a1, a2, nduong, n1, n2, nb1, nb2);
int pass = 0; // for TRACE
if (1)
{
cout << "----------------------" << endl;
cout << "Pass " << ++pass << endl;
Print("a1", a1, n1);
Print("a2", a2, n2);
}
Init(duong1, n); Init(duong2, n);
int nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2);
while (nduong1 >= 1 || nduong2 >= 1)
{
if (nduong1 > nduong2) maxlength = nduong1;
else maxlength = nduong2;
if (temp == 0)
{
n1 = 0; n2 = 0;
nb1 = 0; nb2 = 0;
}
else temp = 0;
if (lan % 2 == 0)
chay2k(a1, a2, b1, b2, maxlength, n, n1, n2, nb1, nb2, duong1, duong2, nduong1, nduong2);
else chay2k(b1, b2, a1, a2, maxlength, n, nb1, nb2, n1, n2, duong1, duong2, nduong1, nduong2);
if (1)
{
cout << "----------------------" << endl;
cout << "Pass " << ++pass << endl;
Print("a1", a1, n1);
Print("a2", a2, n2);
Print("b1", b1, nb1);
Print("b2", b2, nb2);
}
if (lan % 2 == 1)
{
if (stop2k(a, a1, a2, b1, b2, duong1, duong2, n1, n2, nduong1, nduong2, temp, nb1, nb2)) break;
}
else
{
if (stop2k(a, b1, b2, a1, a2, duong1, duong2, nb1, nb2, nduong1, nduong2, temp, n1, n2)) break;
}
lan++;
}
}
// 3k---------------------------------------------------------------------------------------------------------------
void chay3k(int a1[], int a2[], int a3[], int b1[], int b2[], int b3[], int maxlength, int n,
int& n1, int& n2, int& n3, int& nb1, int& nb2, int&nb3,
int duong1[], int duong2[], int duong3[], int& nduong1, int& nduong2, int& nduong3)
{
int j = 1;
Init(b1, n); Init(b2, n); Init(b3, n);
while (j <= maxlength)
{
int *temp = new int[n], ntemp = 0;
Init(temp, n);
if (duong1[j] != -1 || duong2[j] != -1)
{
ntemp = tronAvaoB(temp, ntemp, duong1, a1, j, n);
ntemp = tronAvaoB(temp, ntemp, duong2, a2, j, n);
ntemp = tronAvaoB(temp, ntemp, duong3, a3, j, n);
if (j % 3 == 1) nb1 = ganAvaoB(temp, b1, -1, ntemp, nb1) - 1;
else if(j % 3 == 2) nb2 = ganAvaoB(temp, b2, -1, ntemp, nb2) - 1;
else nb3 = ganAvaoB(temp, b3, -1, ntemp, nb3) - 1;
}
j++;
}
n1 = 0; n2 = 0; n3 = 0;
}
void phanphoi3k(int a[], int duong[], int a1[], int a2[], int a3[], int nduong,
int& n1, int& n2, int& n3, int& nb1, int& nb2, int& nb3)
{
n1 = 0; n2 = 0; nb1 = 0; nb2 = 0;
for (int i = 0; i < nduong; i++)
{
if (i % 3 == 0) n1 = ganAvaoB(a, a1, duong[i], duong[i + 1], n1);
else if(i % 3 == 1) n2 = ganAvaoB(a, a2, duong[i], duong[i + 1], n2);
else n3 = ganAvaoB(a, a3, duong[i], duong[i + 1], n3);
}
}
bool stop3k(int a[], int a1[], int a2[], int a3[], int b1[], int b2[], int b3[],
int duong1[], int duong2[], int duong3[], int& n1, int& n2, int& n3,
int& nduong1, int& nduong2, int& nduong3, int& temp, int& nb1, int& nb2, int& nb3)
{
bool IsRedo = false;
nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3);
if (nduong1 == 1 && nduong2 == 1 && nduong3 == 1 &&
(n1 == 0 || (n2 == 0 && n3 == 0)) &&
(n2 == 0 || (n1 == 0 && n3 == 0)) &&
(n3 == 0 || (n1 == 0 && n2 == 0))
)
{
if (n2 == 0 && n3 == 0) ganAvaoB(a1, a, -1, n1 - 1, 0);
else if(n1 == 0 && n3 == 0) ganAvaoB(a2, a, -1, n2 - 1, 0);
else if(n1 == 0 && n2 == 0) ganAvaoB(a3, a, -1, n3 - 1, 0);
return true;
}
else if(nduong1 == 1 && n1 == 0 && nduong3 == 1 && n3 == 0)
{
phanphoi3k(a2, duong2, b1, b2, b3, nduong2, n1, n2, n3, nb1, nb2, nb3);
temp = 1;
IsRedo = true;
}
else if(nduong2 == 1 && n2 == 0 && nduong3 == 1 && n3 == 0)
{
phanphoi3k(a1, duong1, b1, b2, b3, nduong1, nb1, nb2, nb3, n1, n2, n3);
temp = 1;
IsRedo = true;
}
else if(nduong2 == 1 && n2 == 0 && nduong1 == 1 && n1 == 0)
{
phanphoi3k(a3, duong3, b1, b2, b3, nduong3, nb1, nb2, nb3, n1, n2, n3);
temp = 1;
IsRedo = true;
}
if (!IsRedo) nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3);
else nduong1 = demduong(b1, duong1, nb1), nduong2 = demduong(b2, duong2, nb2), nduong3 = demduong(b3, duong3, nb3);
return false;
}
void MergeSort3k(int a[], int n)
{
int *a1 = new int[n], *a2 = new int[n], *a3 = new int[n], *b1 = new int[n], *b2 = new int[n], *b3 = new int[n];
int *duong1 = new int[n], *duong2 = new int[n], *duong3 = new int[n];
int n1 = 0, n2 = 0, n3 = 0, temp = 0, nb1 = 0, nb2 = 0, nb3 = 0, lan = 0, maxlength = 0;
Init(duong1, n);
int nduong = demduong(a, duong1, n);
phanphoi3k(a, duong1, a1, a2, a3, nduong, n1, n2, n3, nb1, nb2, nb3);
int pass = 0; // for TRACE
if (1)
{
cout << "----------------------" << endl;
cout << "Pass " << ++pass << endl;
Print("a1", a1, n1);
Print("a2", a2, n2);
Print("a3", a3, n3);
}
Init(duong1, n); Init(duong2, n); Init(duong3, n);
int nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3);
while (nduong1 >= 1 || nduong2 >= 1 || nduong3 >= 1)
{
if (nduong1 > nduong2) maxlength = nduong1;
else maxlength = nduong2;
if (maxlength < nduong3) maxlength = nduong3;
if (temp == 0)
{
n1 = 0; n2 = 0; n3 = 0;
nb1 = 0; nb2 = 0; nb3 = 0;
}
else temp = 0;
if (lan % 2 == 0)
chay3k(a1, a2, a3, b1, b2, b3, maxlength, n, n1, n2, n3, nb1, nb2, nb3, duong1, duong2, duong3, nduong1, nduong2, nduong3);
else chay3k(b1, b2, b3, a1, a2, a3, maxlength, n, nb1, nb2, nb3, n1, n2, n3, duong1, duong2, duong3, nduong1, nduong2, nduong3);
if (1)
{
cout << "----------------------" << endl;
cout << "Pass " << ++pass << endl;
Print("a1", a1, n1);
Print("a2", a2, n2);
Print("a3", a3, n3);
Print("b1", b1, nb1);
Print("b2", b2, nb2);
Print("b3", b3, nb3);
}
if (lan % 2 == 1)
{
if (stop3k(a, a1, a2, a3, b1, b2, b3, duong1, duong2, duong3, n1, n2, n3, nduong1, nduong2, nduong3, temp, nb1, nb2, nb3)) break;
}
else
{
if (stop3k(a, b1, b2, b3, a1, a2, a3, duong1, duong2, duong3, nb1, nb2, nb3, nduong1, nduong2, nduong3, temp, n1, n2, n3)) break;
}
lan++;
}
}
// 4k-----------------------------------------------------------------------------------------------------------------------------
void chay4k(int a1[], int a2[], int a3[], int a4[], int b1[], int b2[], int b3[], int b4[], int maxlength, int n,
int& n1, int& n2, int& n3, int& n4, int& nb1, int& nb2, int& nb3, int& nb4,
int duong1[], int duong2[], int duong3[], int duong4[], int& nduong1, int& nduong2, int& nduong3, int& nduong4)
{
int j = 1;
Init(b1, n); Init(b2, n); Init(b3, n); Init(b4, n);
while (j <= maxlength)
{
int *temp = new int[n], ntemp = 0;
Init(temp, n);
if (duong1[j] != -1 || duong2[j] != -1 || duong3[j] != -1 || duong4[j] != -1)
{
ntemp = tronAvaoB(temp, ntemp, duong1, a1, j, n);
ntemp = tronAvaoB(temp, ntemp, duong2, a2, j, n);
ntemp = tronAvaoB(temp, ntemp, duong3, a3, j, n);
ntemp = tronAvaoB(temp, ntemp, duong4, a4, j, n);
if (j % 4 == 1) nb1 = ganAvaoB(temp, b1, -1, ntemp, nb1) - 1;
else if(j % 4 == 2) nb2 = ganAvaoB(temp, b2, -1, ntemp, nb2) - 1;
else if(j % 4 == 3) nb3 = ganAvaoB(temp, b3, -1, ntemp, nb3) - 1;
else nb4 = ganAvaoB(temp, b4, -1, ntemp, nb4) - 1;
}
j++;
}
n1 = 0; n2 = 0; n3 = 0; n4 = 0;
}
void phanphoi4k(int a[], int duong[], int a1[], int a2[], int a3[], int a4[], int nduong,
int& n1, int& n2, int& n3, int& n4, int& nb1, int& nb2, int& nb3, int& nb4)
{
n1 = 0; n2 = 0; n3 = 0; n4 = 0; nb1 = 0; nb2 = 0; nb3 = 0; nb4 = 0;
for (int i = 0; i < nduong; i++)
{
if (i % 4 == 0) n1 = ganAvaoB(a, a1, duong[i], duong[i + 1], n1);
else if(i % 4 == 1) n2 = ganAvaoB(a, a2, duong[i], duong[i + 1], n2);
else if(i % 4 == 2) n3 = ganAvaoB(a, a3, duong[i], duong[i + 1], n3);
else n4 = ganAvaoB(a, a4, duong[i], duong[i + 1], n4);
}
}
bool stop4k(int a[], int a1[], int a2[], int a3[], int a4[], int b1[], int b2[], int b3[], int b4[],
int duong1[], int duong2[], int duong3[], int duong4[], int& n1, int& n2, int& n3, int& n4,
int& nduong1, int& nduong2, int& nduong3, int& nduong4, int& temp, int& nb1, int& nb2, int& nb3, int& nb4)
{
bool IsRedo = false;
nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2); nduong3 = demduong(a3, duong3, n3), nduong4 = demduong(a4, duong4, n4);
if (nduong1 == 1 && nduong2 == 1 && nduong3 == 1 && nduong4 == 1 &&
(n1 == 0 || (n2 == 0 && n3 == 0 && n4 == 0)) &&
(n2 == 0 || (n1 == 0 && n3 == 0 && n4 == 0)) &&
(n3 == 0 || (n1 == 0 && n2 == 0 && n4 == 0)) &&
(n4 == 0 || (n1 == 0 && n2 == 0 && n3 == 0))
)
{
if (n2 == 0 && n3 == 0 && n4 == 0) ganAvaoB(a1, a, -1, n1 - 1, 0);
else if(n1 == 0 && n3 == 0 && n4 == 0) ganAvaoB(a2, a, -1, n2 - 1, 0);
else if(n1 == 0 && n2 == 0 && n4 == 0) ganAvaoB(a3, a, -1, n3 - 1, 0);
else if(n1 == 0 && n2 == 0 && n3 == 0) ganAvaoB(a4, a, -1, n4 - 1, 0);
return true;
}
else if(nduong1 == 1 && n1 == 0 && nduong3 == 1 && n3 == 0 && nduong4 == 1 && n4 == 0)
{
phanphoi4k(a2, duong2, b1, b2, b3, b4, nduong2, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
temp = 1;
IsRedo = true;
}
else if(nduong2 == 1 && n2 == 0 && nduong3 == 1 && n3 == 0 && nduong4 == 1 && n4 == 0)
{
phanphoi4k(a1, duong1, b1, b2, b3, b4, nduong1, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
temp = 1;
IsRedo = true;
}
else if(nduong2 == 1 && n2 == 0 && nduong1 == 1 && n1 == 0 && nduong4 == 1 && n4 == 0)
{
phanphoi4k(a3, duong3, b1, b2, b3, b4, nduong3, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
temp = 1;
IsRedo = true;
}
else if(nduong1 == 1 && n1 == 0 && nduong2 == 1 && n2 == 0 && nduong3 == 1 && n3 == 0)
{
phanphoi4k(a4, duong4, b1, b2, b3, b4, nduong3, nb1, nb2, nb3, nb4, n1, n2, n3, n4);
temp = 1;
IsRedo = true;
}
if (!IsRedo) nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3), nduong4 = demduong(a4, duong4, n4);
else nduong1 = demduong(b1, duong1, nb1), nduong2 = demduong(b2, duong2, nb2), nduong3 = demduong(b3, duong3, nb3), nduong4 = demduong(b4, duong4, nb4);
return false;
}
void MergeSort4k(int a[], int n)
{
int *a1 = new int[n], *a2 = new int[n], *a3 = new int[n], *a4 = new int[n], *b1 = new int[n], *b2 = new int[n], *b3 = new int[n], *b4 = new int[n];
int *duong1 = new int[n], *duong2 = new int[n], *duong3 = new int[n], *duong4 = new int[n];
int n1 = 0, n2 = 0, n3 = 0, n4 = 0, temp = 0, nb1 = 0, nb2 = 0, nb3 = 0, nb4 = 0, lan = 0, maxlength = 0;
Init(duong1, n);
int nduong = demduong(a, duong1, n);
phanphoi4k(a, duong1, a1, a2, a3, a4, nduong, n1, n2, n3, n4, nb1, nb2, nb3, nb4);
int pass = 0; // for TRACE
if (1)
{
cout << "----------------------" << endl;
cout << "Pass " << ++pass << endl;
Print("a1", a1, n1);
Print("a2", a2, n2);
Print("a3", a3, n3);
Print("a3", a4, n4);
}
Init(duong1, n); Init(duong2, n); Init(duong3, n); Init(duong4, n);
int nduong1 = demduong(a1, duong1, n1), nduong2 = demduong(a2, duong2, n2), nduong3 = demduong(a3, duong3, n3), nduong4 = demduong(a4, duong4, n4);
while (nduong1 >= 1 || nduong2 >= 1 || nduong3 >= 1 || nduong4 >= 1)
{
if (nduong1 > nduong2) maxlength = nduong1;
else maxlength = nduong2;
if (nduong3 > maxlength) maxlength = nduong3;
if (nduong4 > maxlength) maxlength = nduong4;
if (temp == 0)
{
n1 = 0; n2 = 0; n3 = 0; n4 = 0;
nb1 = 0; nb2 = 0; nb3 = 0; nb4 = 0;
}
else temp = 0;
if (lan % 2 == 0)
chay4k(a1, a2, a3, a4, b1, b2, b3, b4, maxlength, n, n1, n2, n3, n4, nb1, nb2, nb3, nb4, duong1, duong2, duong3, duong4, nduong1, nduong2, nduong3, nduong4);
else chay4k(b1, b2, b3, b4, a1, a2, a3, a4, maxlength, n, nb1, nb2, nb3, nb4, n1, n2, n3, n4, duong1, duong2, duong3, duong4, nduong1, nduong2, nduong3, nduong4);
if (1)
{
cout << "----------------------" << endl;
cout << "Pass " << ++pass << endl;
Print("a1", a1, n1);
Print("a2", a2, n2);
Print("a3", a3, n3);
Print("a4", a4, n4);
Print("b1", b1, nb1);
Print("b2", b2, nb2);
Print("b3", b3, nb3);
Print("b4", b4, nb4);
}
if (lan % 2 == 1)
{
if (stop4k(a, a1, a2, a3, a4, b1, b2, b3, b4, duong1, duong2, duong3, duong4, n1, n2, n3, n4, nduong1, nduong2, nduong3, nduong4, temp, nb1, nb2, nb3, nb4)) break;
}
else
{
if (stop4k(a, b1, b2, b3, b4, a1, a2, a3, a4, duong1, duong2, duong3, duong4, nb1, nb2, nb3, nb4, nduong1, nduong2, nduong3, nduong4, temp, n1, n2, n3, n4)) break;
}
lan++;
}
}
void main()
{
if (TRACE)
{
//int a[] = {3,5,2,7,12,8,4,15,20,1,2,8,23,7,21,27};
//int a[] = {5,1,2,8,4,17,10,12,4,3,24,1,4};
int a[] = { 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int n = sizeof(a) / sizeof(*a);
cout << "------- BEFORE -------" << endl;
Print("a", a, n);
MergeSort2k(a, n);
//MergeSort3k(a, n);
//MergeSort4k(a, n);
cout << "------- AFTER -------" << endl;
Print("a", a, n);
_getch();
}
else
{
// read init data from textfile
int n;
int* a = InitRandom(n);
if (!a) return; // a == NULL
// sort data
long start = clock();
MergeSort2k(a, n);
//MergeSort3k(a, n);
//MergeSort4k(a, n);
long end = clock();
cout << "10.MergeSort.BalancedMultiway is OK --> elapsed time = " << (end - start) << " (ms) !!!" << endl;
// write sorted data to textfile
Write2TextFile(a, n, "output.txt");
_getch();
}
}