Внешняя многофазная сортировка

[Aндрей]

Вобшем написал программу по этому алгоритму http://www.algolib.narod.ru/Sort/PolyPhaseMerge.html . Она вроде более менее работает, хотя косяков в ней хватает. Объясните как лучше память распределять на втором этапе, потому что если в исходном файле оч много данных, то если использовать динамические массивы, в них не хватает места потом на опред этапах и выводятся левые числа. Ну и вообще помогите пожалуйста исправить хоть приблизительно алгоритм, если я что-то совсем неправильно организовал. На первом этапе вроде все правильно работает. Со втором не уверен, сделал, чтобы он выполнялся, пока второй из файлов B или D не будет пустой. Пишу в среде BC31.

#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#include <fstream.h>

int empty(char *str)
{
	 char *s;
	 ifstream file(str);
	 file>>s;
	 if(s[0]=='\0')
			return 1;
	 return 0;
}

void show(char *str)
{
   int mas[100];
	 ifstream file(str);
	 int i=0;
	 while(!file.eof())
	 {
			file>>mas[i];
			if(!file.eof())
			{
				 cout<<mas[i]<<" ";
				 i++;
			}
	}
	file.close();
  cout<<endl;
}

void write(char *str, int *mas, int &size)
{
	 ofstream file(str,ios::app);
	 int v=0;
	 while(v<size)
	 {
			file<<mas[v]<<"  ";
			v++;
	 }
	 file.close();
}

void sort(int *mas, int &i)
{
	 int j=0, temp, izm=1, hod=0;
	 while((hod<i)&&(izm!=0))
	 {
			izm=0;
			j=0;
			while(j<(i-1))
			{
				 if(mas[j]>mas[j+1])
				 {
						temp=mas[j];
						mas[j]=mas[j+1];
						mas[j+1]=temp;
						izm=1;
				 }
				 j++;
			}
			hod++;
	 }
}

void main(void)
{
	ofstream file2("A.txt");
	file2<<"";
	file2.close();
	ofstream file3("B.txt");
	file3<<"";
	file3.close();
	ofstream file4("C.txt");
	file4<<"";
	file4.close();
	ofstream file5("D.txt");
	file5<<"";
	file5.close();
	clrscr();
	//char *str, *str1, *str2;
	int const S=2;
	int i=0, mas[S], CurrentFile=1, flag=0;
	//cout << " Enter a way and file name: "; cin >> str;
	//cout << " Enter a way and file name for file A: "; cin >> str2;
	//cout << " Enter a way and file name for file B: "; cin >> str3;
	ifstream file("111.txt");
	while(!file.eof())
	{
		 i=0;
		 while((flag!=1) && (i<S))
		 {
				file>>mas[i];
				flag=(!file.eof())?0:1;
				if(flag!=1)
					 i++;
				else
					 break;
		 }

		 if(flag!=1)
		 {
				int j;
				sort(mas,i);
				if(CurrentFile==1)
				{
					 write("A.txt",mas,i);
					 CurrentFile=0;
				}
				else
				{
					 write("B.txt",mas,i);
					 CurrentFile=1;
				}
		 }

		 if((flag==1)&&(i!=0))
		 {
				int j;
				sort(mas,i);
				if(CurrentFile==1)
				{
					 write("A.txt",mas,i);
					 CurrentFile=0;
				}
				else
				{
					 write("B.txt",mas,i);
					 CurrentFile=1;
				}
		 }
	}
	cout<<"File: ";
	show("111.txt");
           cout<<"A: ";
	show("A.txt");
	cout<<"B: ";
	show("B.txt");
	//////////////////////////////////////////////////////////////////////////


	int Size=S;
	int Input=1;//, Input2=2;
	ifstream InputFile1("A.txt");
	ifstream InputFile2("B.txt");
	int CurrentOutput=3;

	int change=1;
	while(change!=0)
	{
		 change=0;
		 int const razm=Size+2;//Size*2;
		 int const r=(Size/2)+2;
		 int *mas1=new int[r], *mas2=new int[r], *masres=new int[razm], fl=0,fl2=0;
		 int ch=0;
		 while((!InputFile1.eof())&&(!InputFile2.eof()))
		 {
				ch++;
				int i,j;
				if(fl!=1)
				{
					 i=0;
					 while(i<(Size/2))
					 {
							InputFile1>>mas1[i];
							fl=(!InputFile1.eof())?0:1;
							if(fl!=1)
								 i++;
							else
							{
								 j=0;
								 while(fl2!=1)
								 {
										InputFile2>>mas2[j];
										fl2=(!InputFile2.eof())?0:1;
										if(fl2!=1)
											 j++;
								 }
								 break;
							}
					 }
				}
				if(fl2!=1)
				{
					 j=0;
					 while(j<(Size/2))
					 {
							InputFile2>>mas2[j];
							fl2=(!InputFile2.eof())?0:1;
							if(fl2!=1)
								 j++;
							else
							{
								 //i=0;
								 while(fl!=1)
								 {
										InputFile1>>mas1[i];
										fl=(!InputFile1.eof())?0:1;
										if(fl!=1)
											 i++;
								 }
								 break;
							}
					 }
				}

				int size=i+j;
				memcpy(masres,mas1,i*sizeof(int));
				memcpy(&masres[i],mas2,j*sizeof(int));
				sort(masres,size);

[Aндрей]

продолжение

				if(CurrentOutput==1)				// if A
				{
					 write("A.txt",masres,size);
					 if(ch==2)
					 {
							CurrentOutput=2; 		// then B
							ch=0;
					 }
				}
				else
				{
					 if(CurrentOutput==2)		// if B
					 {
							//change=1;
							write("B.txt",masres,size);
							if(ch==2)
							{
								 CurrentOutput=1; 	// then A
								 //change=1;
								 ch=0;
							}
					 }
					 else
					 {
							if(CurrentOutput==3)		// if C
							{
								 write("C.txt",masres,size);
								 if(ch==2)
								 {
										CurrentOutput=4; // then D
										ch=0;
								 }
							}
							else
							{
								 if(CurrentOutput==4)		// if D
								 {
										//change=1;
										write("D.txt",masres,size);
										if(ch==2)
										{
											 CurrentOutput=3;  // then C
											 //change=1;
											 ch=0;
										}
								 }
							}
					 }
				}
		 }

		 delete []mas1;
		 delete []mas2;
		 delete []masres;
		 InputFile1.close();
		 InputFile2.close();

		 if(CurrentOutput==1)
		 {
				if(empty("B.txt")!=1)
					 change=1;
		 }
		 else
		 {
				if(empty("D.txt")!=1)
					 change=1;
		 }


		 if(change==0)
		 {
				if(CurrentOutput==1)
				{
					//if(empty("B.txt")==1)
					 //{
							cout<<"A: ";
							show("A.txt");
							cout<<"B: ";
							show("B.txt");
					 //}
					 //else change=1;
				}
				else
				{
					 //if(empty("D.txt")==1)
					 //{
							cout<<"C: ";
							show("C.txt");
							cout<<"D: ";
							show("D.txt");
					 //}
					 //else change=1;
				}
		 }


		 Size*=2;
		 if(change!=0)
		 {
				if(Input==1)
				{
					 Input=3;
					 CurrentOutput=1;
					 ofstream file("A.txt");
					 file<<"";
					 file.close();
					 ofstream file2("B.txt");
					 file2<<"";
					 file2.close();
					 fl=0;fl2=0;
					 cout<<"C: ";
					 show("C.txt");
					 cout<<"D: ";
					 show("D.txt");
					 InputFile1.open("C.txt");
					 InputFile2.open("D.txt");
				}
				else
				{
					 Input=1;
					 CurrentOutput=3;
					 ofstream file("C.txt");
					 file<<"";
					 file.close();
					 ofstream file2("D.txt");
					 file2<<"";
					 file2.close();
					 fl=0;fl2=0;
					 cout<<"A: ";
					 show("A.txt");
					 cout<<"B: ";
					 show("B.txt");
					 InputFile1.open("A.txt");
					 InputFile2.open("B.txt");
				}
		 }
	}

	getch();
}

Для данных 4 2 9 0 5 1 6 3 8 7 вроде работает.