Merge Sort using recursion

Question

I tried to implement a recursive merge-sort, but I get a stack overflow error.

public class MergeSort {
    static int input[],mid;
    public static void mergeSort(int input[],int start,int end ){
        if(start>end){
            return;
        }
// dividing input array into two equal parts
        mid=(start+end)/2;
        mergeSort(input,start,mid);
        mergeSort(input,mid+1,end);
        merge(input,start,mid,end);
    }
    public static void merge(int input[],int start,int mid,int end )
    {
        int l[]=new int[mid-start+1];
        int r[]=new int[end-mid];
        for(int i=1;i<end-start+1;i++){
            l[i]=input[start+i-1];
        }
        for(int j=1;j<end-mid;j++){
            r[j]=input[mid+j];
        }

    l[end-start+2]='\u221e';// ASCII vlaue of infinity at the end of left array
    r[end-mid+1]='\u221e';//ASCII vlaue of infinity at the end of right array
    int i=1,j=1;
    for(int k=start;k<end;k++){
        if(l[i]<=r[j]){
            input[k]=l[i];
            i=i+1;
        }
        else{
            input[k]=r[j];
            j=j+1;
        }
    }

If you understand what StackOverflow means, that should hint you where the problem lies. — Yuval Filmus
– Yuval Filmus, Commented Jul 17, 2017 at 14:13
How big is the interval you are testing? Do you even have a StackOverflow on small inputs? If no, is the resulting output even correct? If it also happens on small inputs than you probably have an error on your recursion strategy. Try checking if you call the method on the correct indices and also if your stop criterion is correct. StackOverflow indicates that your recursion either will not halt or is just too big to compute (e.g. out of memory). Check the code against pseudo-code from Wikipedia, for example: en.wikipedia.org/wiki/Merge_sort — Zabuzard
– Zabuzard, Commented Jul 17, 2017 at 14:23
Where is the trace from your debugging efforts? If nothing else, stick a trivial print command at the top of each method to display the input arguments. That much will tell you a lot about the recursion progression. — Prune
– Prune, Commented Jul 17, 2017 at 20:53

Prune · Accepted Answer · 2017-07-17 20:58:39Z

2

The problem is your termination condition:

    if(start > end){
        return;
    }
    // dividing input array into two equal parts
    mid=(start+end)/2;
    mergeSort(input,start,mid);   //  <= infinite recursion
    mergeSort(input,mid+1,end);

In the first recursion, there is no way to reduce mid (the next end value) to be less than start. For instance, starting with the range [0, 6], here is the sequence of start, end values for the first recursive call:

0 6    mid = (0+6)/2 = 3
0 3    mid = (0+3)/2 = 1
0 1    mid = (0+1)/2 = 0
0 0    mid = (0+0)/2 = 0
0 0    mid = (0+0)/2 = 0
...

You never get to a point where start > end. Infinite recursion.

Perhaps start >= end would work for you? That makes your base case a 1-item array, rather than an empty array.

answered Jul 17, 2017 at 20:58

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

EJoshuaS - Stand with Ukraine Over a year ago

Nice explanation of why this is infinite recursion (better than mine I think), I'll upvote once I get more votes.

EJoshuaS - Stand with Ukraine · Accepted Answer · 2017-07-17 21:06:03Z

1

You have infinite recursion. Look at the calls carefully:

if(start>end){
        return;
    }
 // dividing input array into two equal parts
    mid=(start+end)/2;
    mergeSort(input,start,mid);
    mergeSort(input,mid+1,end);
    merge(input,start,mid,end);

You're always passing the same value of start for the first call - you never actually change it - and mid can never be less than start. Thus, your terminating condition can never hold and this is infinite recursion.

edited Jul 17, 2017 at 21:06

answered Jul 17, 2017 at 14:26

EJoshuaS - Stand with Ukraine

12.2k63 gold badges59 silver badges86 bronze badges

3 Comments

Prune Over a year ago

I don't think that's correct: the code does change start in the 2nd call and changes end in the 1st. Note that merge is not recursive. This is the basic merge-sort principle: sort each half individually; then merge the results.

EJoshuaS - Stand with Ukraine Over a year ago

@Prune But for the first call (mergeSort(input, start, mid)) is, in fact, infinite because there's no way for start > end to be true.

EJoshuaS - Stand with Ukraine Over a year ago

@Prune Looking at this again I probably could've phrased it more clearly, I'll edit.

Collectives™ on Stack Overflow

Merge Sort using recursion

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related