Thread: Sorting a very large list

I'm quite new to programming, please excuse my mistakes.

So for my programming project this semester I got a file containing temperature data from all countries in the world, the uncertainty related to that measurement and the date of measure.

I have to upload all of that data to a double linked sorted list. Basically the list has around 600 000 elements (nodes). Each node contains a next pointer, a prev pointer and some data ( as usual, i guess). I have to sort the list by year, so basically it goes node->payload.date.year.

I tried to use the insertion sort alone, but it took me more than 20 minutes to sort it.

I came up with this "algorithm" where I would have an array of structures containing pointers to the middle of the list, so that I wouldn't have to iterate from the head, every single time. I thought saving pointers for each year was reasonable (there are around 200 years).So the structure has a pointer of the type node and it also has an integer (year) as a tag.

If, by now, you have spotted some huge mistake or a hole in my idea, maybe you don't have to look at the code. If it's minimally reasonable, I would appreciate if you did.

The thing is, my new array of structures is messing with the original list. On top of the segmentation fault which ends the execution, the original list dates are being changed.

Code:

void InsertSort(node_t ** _head, dados_temp* _fcountries, pointers_years **pointers, int *count){
    node_t *new_elem = NULL;
    node_t *iterador = NULL;
    new_elem = NewNode(_fcountries);


    int aux=0, i=0, j=0, found=0;


    if(*_head == NULL)
    {
        *_head = new_elem;
    
        *pointers = (pointers_years*)checkedMAlloc(sizeof(pointers_years));


        pointers[0]->year = new_elem->payload.dt.year;
        pointers[0]->pointer = new_elem;


        (*count)++;




        return;
    }


    for(i=0;i<(*count);i++)
    {
        if( (new_elem->payload.dt.year) == (pointers[i]->year))
        {
            iterador = pointers[i]->pointer;
            found=1;
            break;
        }
        else
        {
            found=0;
        }
    }
    if(found==0)
    {
        *pointers = (pointers_years*)realloc(*pointers,sizeof(pointers_years)*(i+1));


        pointers[i]->year = new_elem->payload.dt.year;
        pointers[i]->pointer = new_elem;


        aux = abs(pointers[0]->year-pointers[i]->year);
        iterador=*_head;
        for(j=0;j<*count;j++)
        {
            if(abs(pointers[j]->year-pointers[i]->year)<aux && (pointers[j]->year)<(pointers[i]->year))
            {
                aux=abs(pointers[j]->year-pointers[i]->year);
                iterador=pointers[j]->pointer;
            }
        }
        (*count)++;
    }




    while(date_cmp(iterador,new_elem)<0) // if iterator < new element
    {
        if(iterador->next!=NULL)
            iterador=iterador->next;
        else // if we have reached the last node of the list
        {
            iterador->next=new_elem;
            new_elem->prev = iterador;
            return;
        }
    }


    if(iterador==*_head )
    {
        new_elem->next=iterador;
        iterador->prev=new_elem;
        (*_head)=new_elem;
    }
    else if (iterador==pointers[j]->pointer)
    {
        new_elem->prev=iterador->prev;
        iterador->prev->next=new_elem;
        new_elem->next=iterador;
        iterador->prev=new_elem;
        pointers[j]->pointer=new_elem;
    }
    else
    {
         new_elem->next=iterador;
         new_elem->prev=iterador->prev;
         iterador->prev->next=new_elem;
         iterador->prev=new_elem;
    }
}

I realise it may be very confusing, I am sorry.

If you need to see the function where I call this one (the function that reads from the file and send the data to an auxiliar structure named _fcountries), just say it.

Also here's put a print from the terminal after i compile this.



The first two ones are okay, the third is obviously not okay. Also, it should print way more than three!