Infinite recursion in Merge Sort

indyarock (3)
Hi,
I'm trying to implement a merge sort as follows:
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
 
// Merge sort
//lb = lower bound, ub = upper bound, temp = temporary array, data[]= input array
//Maximum function
template<class T>
T Max(T &x, T &y)
{
    if(x > y)
    return x;
    else
    return y;
}

//To divide
template<class T>
void MergeFunction(T *data,int lb, int ub)
{
    int Mid;
    if(lb < ub)
    {
        Mid = (lb+ub)/2;
        MergeFunction(data,lb,lb+Mid);
        MergeFunction(data,lb+Mid+1,ub);
        MergeSortHelper(data,lb,Mid,ub);
    }
}
//To sort the divided array
template<class T>
void MergeSortHelper(T *data,int lb, int Mid, int ub)
{
    int l = lb;
    int r = Mid+1;
    T temp[ub - lb + 1];
    for(int k = 0; k <= ub-lb; k++)
    {
        if(l < Mid+1 && (r == ub || Max(data[l],data[r]) == data[l]))
           {
               temp[k] = data[l];
               l++;
           }
        else
            {
                temp[k] = data[r];
                r++;
            }
    }

    for(int i = 0; i <= ub - lb; i++)
    data[lb+i] = temp[i];
}

template<class T>
void MergeSort(T *data, int size)
{
        MergeFunction(data,0,size-1);
}

But its going in infinite loop.
Here is the stack call:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#0 00000000	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:16)
#1 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#2 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#3 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#4 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#5 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#6 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#7 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#8 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#9 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#10 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=8) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#11 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=7) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#12 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=6) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#13 0041D227	MergeFunction<int>(data=0x28fe6c, lb=3, ub=4) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#14 0041D249	MergeFunction<int>(data=0x28fe6c, lb=0, ub=4) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:20)
#15 0041D227	MergeFunction<int>(data=0x28fe6c, lb=0, ub=9) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:19)
#16 0041D5FD	MergeSort<int>(data=0x28fe6c, size=10) (C:/CodeBlock/LinkedList Problems/MergeSort.hpp:51)
#17 00401832	main() (C:\CodeBlock\LinkedList Problems\main.cpp:31)

Can anybody please point out my mistake ?
Last edited on
BlackSheep (424)
1
2
3
4
5
6
7
 
 if(lb < ub) //You test if lb < up here which is the condition to continue.
    {
        Mid = (lb+ub)/2;
        MergeFunction(data,lb,lb+Mid); //But here you pass arguments that will always fulfill this condition.
        MergeFunction(data,lb+Mid+1,ub);
        MergeSortHelper(data,lb,Mid,ub);
    }


EDIT: Nevermind, it should tend to zero. The problem is the second call. You always pass 0, and x where x is size-1. Then mid is just x/2. In your second call you pass 0+Mid+1 which will always be at least 2. Divide by 2 gives you 1, add 1 gives you 2.
Last edited on
indyarock (3)
Thanks BlackSheep. You are right. But how to go about it then ? Any suggestions? Usually this is how, its implemented everywhere. I tried to write it in my own words instead of copying.
Topic archived. No new replies allowed.