C++

Forum

 
Problem Merge Sort For Large n

Farrukh12 (32)
My programs gives a segmentation fault for large n (n=9999999). It works fine for small n. Where n = total numbers to sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
List<long>* Merge(List<long> *ParentList)
{
        if(ParentList->length()==1)
        {
            return ParentList;
        }

    List<long> *LeftList=new List<long>;
    List<long> *RightList=new List<long>;
    List<long> *TempList=new List<long>;

    unsigned int Counter=ParentList->length();
    unsigned int MidPoint=Counter/2;
    ListItem<long> *TempPointer=ParentList->getTail();

        while(Counter!=MidPoint)
        {
            RightList->insertAtHead(TempPointer->value);
            TempPointer=TempPointer->prev;
            Counter--;
        }

        while(TempPointer!=NULL)
        {
            LeftList->insertAtHead(TempPointer->value);
            TempPointer=TempPointer->prev;
        }


    //delete ParentList;

    LeftList=Merge(LeftList);
    RightList=Merge(RightList);

    ListItem<long> *LeftPointer=LeftList->getHead();
    ListItem<long> *RightPointer=RightList->getHead();

            if(LeftPointer->value<=RightPointer->value)
            {
                TempList->insertAtHead(LeftPointer->value);
                LeftPointer=LeftPointer->next;
            }
            else
            {
                TempList->insertAtHead(RightPointer->value);
                RightPointer=RightPointer->next;
            }

        TempPointer=TempList->getHead();

        while((LeftPointer!=NULL) && (RightPointer!=NULL))
        {
            if(LeftPointer->value<=RightPointer->value)
            {
                TempPointer->next=LeftPointer;
                LeftPointer->prev=TempPointer;
                LeftPointer=LeftPointer->next;
                TempPointer=TempPointer->next;
            }
            else
            {
                TempPointer->next=RightPointer;
                RightPointer->prev=TempPointer;
                RightPointer=RightPointer->next;
                TempPointer=TempPointer->next;
            }

        }

        if(RightPointer==NULL)
        {
            TempPointer->next=LeftPointer;
            LeftPointer->prev=TempPointer;
        }
        else
        {
            TempPointer->next=RightPointer;
            RightPointer->prev=TempPointer;
        }

    return TempList;

}
cire (8284)
Increase the stack space that is reserved for your program, or remove recursion.
Farrukh12 (32)
Could there be any other reason? Is there a fault in program.
Major Tom (55)
Nope. Like cire said, you ran out of stack space, which is space the processor uses to preform operations.
Farrukh12 (32)
I have changed my code and declared the Lists on heap but still it gives an error. The following is the divide part:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
List<long>* Merge(List<long> *ParentList)
{
        if((ParentList)->Length==1)
        {
            return ParentList;
        }


    List<long> **LeftList=new List<long>*;
    *LeftList=new List<long>;

    List<long> **RightList=new List<long>*;
    *RightList=new List<long>;

    unsigned long long Counter=0;
    unsigned long long MidPoint=ParentList->Length/2;

    ListItem<long> *TempPointer=(ParentList)->head;
    //cout<<MidPoint<<endl;
        while(Counter!=MidPoint)
        {
            (*LeftList)->insertAtTail(TempPointer->value);
            TempPointer=TempPointer->next;
            Counter++;
//            RightList->insertAtHead(TempPointer->value);
//            TempPointer=TempPointer->prev;
//            Counter--;
        }
        //cout<<(*LeftList)->Length<<endl;
        while(TempPointer!=NULL)
        {
            (*RightList)->insertAtTail(TempPointer->value);
            TempPointer=TempPointer->next;
        }
        //cout<<(*RightList)->Length<<endl;
        //while(1);

    //delete TempPointer;
    //cout<<"FLAG11"<<endl;

    //cout<<"FLAG10"<<endl;
    (*LeftList)=Merge(*LeftList);
    (*RightList)=Merge(*RightList);

    return NULL;
}
Topic archived. No new replies allowed.