Трябва да сортирам списък, използвайки Сортиране чрез сливане, но попаднах на следната грешка.

В списъка ми се съдържат случайни числа. Въпреки това, след сортиране, той показва само числата, които са по-големи от първия елемент на списъка.
Пример:
Числа преди сортиране: 50, 80, 15, 75, 25, 100
Числа след сортиране: 50, 75, 80, 100

Ето и част от кода:

struct elem
{
	int key; 
	elem *next;
} 
*start=NULL;

elem* Split(elem* my_node)
{
    elem* secondNode;

    if (my_node == NULL) return NULL;
    else if (my_node->next == NULL) return NULL;
    else {
        secondNode = my_node->next;
        my_node->next = secondNode->next;
        secondNode->next = Split(secondNode->next);
        return secondNode;
    }
}
elem* Merge(elem* firstNode, elem* secondNode)
{
    if (firstNode == NULL) return secondNode;
    else if (secondNode == NULL) return firstNode;
    else if (firstNode->key <= secondNode->key) //if I reverse the sign to >=, the behavior reverses
    {
        firstNode->next = Merge(firstNode->next, secondNode);
        return firstNode;
    }
    else 
    {
        secondNode->next = Merge(firstNode, secondNode->next);
        return secondNode;
    }
}
elem* MergeSort(elem *my_node)
{
    elem *secondNode;

    if (my_node == NULL)
        return NULL;
    else if (my_node->next == NULL)
        return my_node;
    else
    {
        secondNode = Split(my_node);
        return Merge(MergeSort(my_node),MergeSort(secondNode));
    }
}

Благодаря предварително!

Редактирано 10 януари 201511 г. от Lemondog (преглед на промените)

Провери си останалата част от програмата - според мене сортирането си е наред.

тука скалъпих набързо една функция main() за проверка;

#include <iostream>
#include <ctime>

using namespace std;

struct elem {
     int key;
     elem *next;
} *start;

/***********************/
elem* Split(elem* my_node)
{
    elem* secondNode;

    if (my_node == NULL) return NULL;
    else if (my_node->next == NULL) return NULL;
    else {
        secondNode = my_node->next;
        my_node->next = secondNode->next;
        secondNode->next = Split(secondNode->next);
        return secondNode;
    }
}
elem* Merge(elem* firstNode, elem* secondNode)
{
    if (firstNode == NULL) return secondNode;
    else if (secondNode == NULL) return firstNode;
    else if (firstNode->key <= secondNode->key) //if I reverse the sign to >=, the behavior reverses
    {
        firstNode->next = Merge(firstNode->next, secondNode);
        return firstNode;
    }
    else 
    {
        secondNode->next = Merge(firstNode, secondNode->next);
        return secondNode;
    }
}

elem* MergeSort(elem *my_node)
{
    elem *secondNode;

    if (my_node == NULL)
        return NULL;
    else if (my_node->next == NULL)
        return my_node;
    else
    {
        secondNode = Split(my_node);
        return Merge(MergeSort(my_node),MergeSort(secondNode));
    }
}

/**************************************************/
int main () {
    elem *list=NULL, *n, *p;
    srand(time(NULL));
    for (int i=0; i<200; i++) {
        int t = rand()%900+100;
        cout<<t<<" ";
        p=new elem;
        p->key=t;
        p->next=NULL;
        if (list==NULL) list=p;
        else n->next=p;
        n = p;
    }
    
    list=MergeSort(list);
    cout<<endl<<endl;
    
    p=list;
    while (p) {
        cout<<p->key<<" ";
        n=p;
        p=p->next;
        delete n;
    }
    cout<<endl;
    cin.get();
}

Редактирано 10 януари 201511 г. от ined (преглед на промените)

Ако първото число е по-малко от останалите сортира правилно, но когато не е, трие числата по-малки от него или поне при мен е така.

Ето функциите, които използвам преди да използвам сортирането:

int CreateRandomFile()
{
	int n, i(0), k, num[N];
	srand(time (NULL));
	fstream file1;
	file1.open("Numbers1.txt", ios::out);
	if(file1.fail())
	{
		cout<<"Error!! File not found! ";
	}
	cout<<"Amount of numbers you want to store in the file: ";
	cin>>n;
	while (i<n)
	{
		k=rand() % 100 + 1;
		file1<<k<<endl;
		i++;
	}
	cout<<endl<<n<<" random numbers were stored in your file successful!\n";
	file1.close();
	return 0;
}

void CreateListFromFile()
{
    int b=0;
    ifstream file1;
    file1.open("Numbers1.txt");
    if (file1.is_open())
    {
        while(file1>>b)
        {
            add(b);
        }
    }
        file1.close();
}

void add(int n)
{  
    elem *p=start, *q;  
    q=new elem;
    q->key=n;
    q->next=NULL;
    if (start)
    {
        while(p->next)
            p=p->next;
        p->next=q;
    }
    else
        start=q;          

}

Редактирано 11 януари 201511 г. от Lemondog (преглед на промените)

Да кажем, че са наред, проблема е или където я викаш функцията или след това.

Има неща които не ми харесват, но те не са свързани със сортирането. Начина по който се добавя елемент към списъка не ми харесва, но би трябвало да работи макар че всеки път се обхожда списъка от край до край. Понеже я ползваш само за един единствен списък, можеше да я направиш със static. 

void add(int n)
{  
    static elem *p;
    elem *q;  
    q=new elem;
    q->key=n;
    q->next=NULL;
    if (start) p->next=q;
    else start=q;
    p=q;
}

Освен това при CreateListFromFile() хубаво проверяваш дали се е отворил файла, ама затварянето също трябва да е в този if. При CreateRandomFile() ако има проблем със създаването на файла трябва да се прекрати изпълнението на функцията, а не само да се изкара някакво съобщение и да продължи нататък сякаш се е отворил.

Редактирано 11 януари 201511 г. от ined (преглед на промените)