# 一个很好用的归并排序

//第一天学麻省理工的算法导论，写出了那个归并排序，自己给它添加了好多功能，你只要输入要测试多少组数据，他便会自动生成并将输入写入in.txt中，即使没有它也会自动创建，输出也一样

#include<iostream>
#include<string>
#include<fstream>
#include<time.h>

int len = 0;

using namespace std;

int num[500000];

int random_num(int n);

int write_file_number(int num[]);

bool merge_sort(int num[], int n);
int Merge_Sort(int num[], int first, int last, int temp[]);
int merge_array(int num[], int first, int mid, int last, int temp[]);

int main()
{
clock_t start, end;
start = clock();

int mm;
cout << "请输入数据量：";
cin >> mm;

random_num(mm);

merge_sort(num, len);

for (int i = 0; i < len; ++i)
{
cout << num[i] << ' ';

if ((i + 1) % 10 == 0)
{
cout << endl;
}
}
cout << endl;
write_file_number(num);

end = clock();
cout << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
cout << "only test" << endl;
system("pause");
return 0;
}

int random_num(int n)
{
ofstream out("in.txt", ios::out);
srand((int)time(0));

for (int i = 1; i <= n; ++i)
{
out << rand() << ' ';
if (i % 10 == 0)
{
out << endl;
}
}

out.close();

return 0;
}

{

for (len = 0; !read_file.eof(); ++len)
{
}
len -= 1;

return len;
}

int write_file_number(int num[])
{
ofstream write("out.txt", ios::out);

for (int i = 0; i < len; ++i)
{
write << num[i] << ' ';

if ((i + 1) % 10 == 0)
{
write << endl;
}
}

write.close();

return 0;
}

bool merge_sort(int num[], int n)
{
int * temp = new int[n];

if (temp == nullptr)
{
return false;
}

Merge_Sort(num, 0, n - 1, temp);

delete[] temp;

return true;
}

int Merge_Sort(int num[], int first, int last, int temp[])
{

if (first < last)
{
int mid = (first + last) / 2;

Merge_Sort(num, first, mid, temp);
Merge_Sort(num, mid + 1, last, temp);
merge_array(num, first, mid ,last, temp);

}

return 0;
}

int merge_array(int num[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1, k = 0;

while (i <= mid && j <= last)
{
if (num[i] <= num[j])
{
temp[k++] = num[i++];
}

else
{
temp[k++] = num[j++];
}
}

while(i <= mid)
{
temp[k++] = num[i++];
}

while (j <= last)
{
temp[k++] = num[j++];
}

for (int ij = 0; ij < k; ij++)
{
num[ij + first] = temp[ij];
}

return 0;
}

;