Сортировка слиянием. С++

[Noizik]

Добрый день!
В качестве аргументов командной строки программе передаются два имени файла, в каждом из которых через пробел записаны целые числа (реализо-вать проверку корректности входных данных). Используя класс fstream считать числа из файлов в списки (каждому файлу свой список). Отсорти-ровать полученные два списка по возрастанию, после этого объединить их в один отсортированный список и вывести данные из него в файл file3.txt.
-Двунаправленный связный список. Сортировка слиянием.

Есть программа, реализующая быструю сортировку:

PHP код:

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
struct DoubleList{
    float dataInt;
    DoubleList *Next, *Previous;
};
DoubleList* ReadListFromFile(char fileName[]);
void ShowList(DoubleList *First, int idList, int mode);
int CountItems(DoubleList *First);
void QuickSort(DoubleList *&Head);
void DeleteItem(DoubleList *&Current);
bool isListSeq(DoubleList *Head);
DoubleList* ConnectList(DoubleList *HeadF, DoubleList *HeadS, DoubleList *BreakPoint);
DoubleList* SearchEnd(DoubleList *Head);
DoubleList* ConnectSortList(DoubleList *First, DoubleList *Second);
void WriteListToFile(char fileName[], DoubleList *SortList);
void FreeList(DoubleList *List);
int main(int argc, char* argv[])
{    
    char *fileName1, *fileName2;
    if (argc > 2){
        fileName1 = argv[1];
        fileName2 = argv[2];
    } else {
        fileName1 = "file1.txt";
        fileName2 = "file2.txt";
    }
    DoubleList *FirstList = NULL, *SecondList = NULL;
    FirstList=ReadListFromFile(fileName1);
    SecondList=ReadListFromFile(fileName2); 
    ShowList(FirstList,1,0);
    ShowList(SecondList,2,0);
    system("PAUSE");
    QuickSort(FirstList);
    QuickSort(SecondList);
    ShowList(FirstList,1,1);
    ShowList(SecondList,2,1);
    system("PAUSE");
    DoubleList *Sort = ConnectSortList(FirstList,SecondList);
    ShowList(Sort,1,2);
    WriteListToFile("out.txt", Sort);
    system("PAUSE");
    FreeList(FirstList);
    FreeList(SecondList);
    FreeList(Sort);
    return 0;
}
DoubleList* ReadListFromFile(char *fileName){
    DoubleList *First=NULL;
    ifstream inFile(fileName);
    if (inFile){
        DoubleList *Current=NULL, *Temp=NULL;
        while(!inFile.eof()){
            Current = new DoubleList;
            if (Temp!=NULL) Temp->Next = Current;
            inFile >> Current->dataInt;
            Current->Previous = Temp;
            Current->Next = NULL;
            Temp = Current;
        }
    inFile.close();
    do{
        Current=Current->Previous;
    }
    while(Current->Previous !=NULL);
        First=Current;
    }else cout << "Error on open file: "<<fileName<<endl;
    return First;
}
void ShowList(DoubleList *First, int idList, int mode){
    DoubleList *Current = NULL;
    Current = First;
    int id=1;
    if (mode == 1){
        cout << "List "<<idList<<" [COPTuPOBKA] :\n"; 
    }else if (mode ==2 ){
        cout << "List "<<idList<<" [COEDuHEHuE] :\n"; 
    }else{
        cout << "List "<<idList<<":\n"; 
    }
    do{
        cout <<  ""<<id<<" = "<<Current->dataInt<<endl;
        id++;
        Current = Current->Next;
    }
    while (Current!= NULL);
    cout<<"---------------\n";
}
int CountItems(DoubleList *First){
    DoubleList *Current = First;
    int count = 0;
    while (Current != NULL){
        count++;
        Current = Current->Next;
    }
    return count; 
}
void QuickSort(DoubleList *&Head){
    int idMed;
        if (isListSeq(Head))return;
        int count=CountItems(Head);
        if (count%2 == 0){
            idMed=count/2+1;
        } else {
            idMed=(count+1)/2;
        }
        
        //Находим середину
        DoubleList *BreakPoint=Head;
        for(int i=1; i<idMed;i++){
            BreakPoint=BreakPoint ->Next;
        }
        //Находим конец
        DoubleList *End = SearchEnd(Head);
        DoubleList *Current = NULL, *Temp = NULL;
        //Перекидываем меншие элементы влево
        Current=BreakPoint->Next;
        while(Current!=NULL){
            Temp = Current->Next;
            if (Current->dataInt < BreakPoint->dataInt){
                if (Current == End) End=End->Previous;
                DeleteItem(Current);
                Head->Previous = Current;
                Current->Next = Head;
                Current->Previous = NULL;
                Head = Current;
            }
            Current=Temp;
            if (BreakPoint->Next == NULL) End = BreakPoint;
        }
        //Перекидываем большие элементы вправо
        Current=BreakPoint->Previous;
        while(Current!=NULL){
            Temp = Current->Previous;
            if (Current->dataInt >= BreakPoint->dataInt){
                if (Current==Head) Head = Head->Next;
                DeleteItem(Current);
                End->Next = Current;
                Current->Next = NULL;
                Current->Previous = End;
                End = Current;

            }
            if (BreakPoint->Previous == NULL) Head = BreakPoint;
            Current=Temp;
            
        }    
        End = SearchEnd(Head);
        if (isListSeq(Head))return;
        DoubleList *HeadF=NULL;
        DoubleList *HeadS=NULL;
        if (BreakPoint->Previous != NULL){
            HeadF=Head;
            (BreakPoint->Previous)->Next = NULL;
        }
        if (BreakPoint->Next != NULL){
            HeadS=BreakPoint->Next ;
            HeadS->Previous = NULL;
        }
        if (HeadF !=NULL){
            QuickSort(HeadF);
        }
        if (HeadS !=NULL){
            QuickSort(HeadS);
            }
        Head = ConnectList(HeadF,HeadS,BreakPoint);
}    
} 


[Noizik]

Вторая часть кода:

PHP код:

void DeleteItem(DoubleList *&Current){
        //Если с двух сторон
        if ((Current->Next != NULL)&&(Current->Previous != NULL)){
            (Current->Next)->Previous = Current->Previous;
            (Current->Previous)->Next = Current->Next;
        }
        //Если слева пусто
        if ((Current->Next!=NULL)&&(Current->Previous==NULL)){
            (Current->Next)->Previous = NULL;
        }
        //Если справа пусто
        if ((Current->Next==NULL)&&(Current->Previous!=NULL)){
            (Current->Previous)->Next = NULL;
        }

    }
bool isListSeq(DoubleList *Head){
    bool result = true;
    DoubleList *Current = Head;
    if (Current == NULL) return false;
    while (Current->Next != NULL){
        if(Current->dataInt > (Current->Next)->dataInt ) result = false;
        Current=Current->Next;
    }
    return result;
}
DoubleList* ConnectList(DoubleList *HeadF, DoubleList *HeadS, DoubleList *BreakPoint){
    DoubleList *EndF  = NULL, *Head = NULL;
    if (HeadF != NULL){
        Head = HeadF;
        EndF = SearchEnd(HeadF);
        EndF->Next = BreakPoint;
    }else{
        Head = BreakPoint;
    }
     if (HeadS!= NULL){
        BreakPoint->Next = HeadS;
        HeadS->Previous = BreakPoint;
    }
    return Head;

}
DoubleList* SearchEnd(DoubleList *Head){
    DoubleList *Current = Head;
    while(Current->Next != NULL){
        Current = Current->Next;
    }
    return Current;
    
}

DoubleList* ConnectSortList(DoubleList *First, DoubleList *Second){
    DoubleList *Head = NULL, *Current = NULL;
    //Определяем голову списка
    ShowList(First,1,1);
    ShowList(Second,2,1);
    Head = new DoubleList;
    if (First->dataInt <= Second->dataInt){
        Head->dataInt = First->dataInt;
        Current = Head;
        First = First->Next;
    }else{
        Head->dataInt = Second->dataInt;
        Current = Head;
        Second = Second->Next;
    }
    DoubleList *Temp=NULL;
    //Закидываем в конец списка через сравнение пока два не нулевые
    do {
        Temp = new DoubleList;
        if (First->dataInt <= Second->dataInt){
            Temp->dataInt = First->dataInt;
            First = First->Next;
        }else{
            Temp->dataInt = Second->dataInt;
            Second = Second->Next;
        }
        Current->Next = Temp;
        Temp->Previous = Current;
        Current = Current->Next;
        Current->Next = NULL;
    }
    while ((First!=NULL)&&(Second!=NULL));
    //Как только какойто из списков кончился - конец другого перегоняем в конец результируещего списка
    if (First==NULL){
        do{
            Temp = new DoubleList;
            Temp->dataInt = Second->dataInt;
            Current->Next = Temp;
            Temp->Previous = Current;
            Current = Current->Next;
            Current->Next = NULL;
            Second=Second->Next;    
        }
        while (Second!=NULL);
    } else {
        do{
            Temp = new DoubleList;
            Temp->dataInt = First->dataInt;
            Current->Next = Temp;
            Temp->Previous = Current;
            Current = Current->Next;
            Current->Next = NULL;
            First=First->Next;    
        }
        while (First!=NULL);
    }
    return Head;
}
void WriteListToFile(char fileName[], DoubleList *SortList){
    ofstream OutFile(fileName);
    if (OutFile){
        int value;
        do{
            value = SortList->dataInt;
            OutFile << value <<" ";
            SortList=SortList->Next;
        }
        while (SortList!=NULL);
    }
    OutFile.close();
}
void FreeList(DoubleList *List){
    DoubleList *Current = NULL, *Temp = NULL;
    Current = List;
    do{
        Temp = Current;
        Current = Current->Next;
        delete Temp;
    }
    while (Current!=NULL);

} 


Как реализовать сортировку слиянием, заранее очень благодарен!