Java - merge sort using linked list pointers

Question

I'm having issues implementing a merge sort for a linked list, specifically, the merge part. I'm trying to sort a linked list containing strings and sort them alphabetically. However, my merge code sometimes skips pointers for some reason depending on the order of the original list. Currently I have:

public node merge(node left, node right){
        node result = null;

        if(left == null){
            return right;
        }else if(right == null){
            return left;
        }   

        // The data in the node are stored as strings.
        // Compare if the string in the left node is less that 
        // the string in the right.
        if(left.info.compareTo(right.info) < 0){
            result = left;
            result.next = merge(left.next, right);
        }else{
            result = right;
            result.next = merge(left, right.next);
        }

        return result;
    }

If I had a list that consisted of for example, f->t->c->t->h, my merge will return h->t->t, where pointers are being missed. However, if my list consisted of b->a->t->t->c then it correctly display it alphabetically, a->b->c->t->t, and no pointers are missed.

Any help is appreciated.

Thanks.

why would you not wanna post your split function.. it will definitely help ustand the question better.. — Baz1nga
– Baz1nga, Commented Apr 11, 2012 at 10:07
Any reason why you don't use Java's own LinkedList and Collections.sort(list) to perform that merge sort? — Lukas Eder
– Lukas Eder, Commented Apr 11, 2012 at 10:18
a challenge or an homework probably.. how does that matter? its like giving a jquery soln/why not use jquery to any javascript dom manipulation question.. — Baz1nga
– Baz1nga, Commented Apr 11, 2012 at 10:20

John B · Accepted Answer · 2012-04-11 10:43:23Z

2

I think it is because you are holding the old pointers to left and right which may no longer be the heads to the sub-lists.

Change

 mergeSort(left);
 mergeSort(right);

to

 left = mergeSort(left);
 right = mergeSort(right);

answered Apr 11, 2012 at 10:43

John B

33.1k8 gold badges80 silver badges100 bronze badges

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

1 Comment

user1280446 Over a year ago

That seemed to have fixed it. I just tested it against lists containing one node, two nodes, odd/even number of nodes, and everything seems to work perfectly. Thank you.

pcalcao · Accepted Answer · 2012-04-11 10:45:11Z

1

This probably isn't worth an answer, but here it is.

It's a bit hard to figure out what's going on there, I for one didn't notice any glaring mistakes in the implementation (although I wouldn't use recursion on the merge part, it's simpler to implement it "iteratively").

In my opinion, you need to figure out what's going on step by step. If you know a couple of examples that work and that don't work (seems like you do), call each method directly with the expected input.

For instance, to figure out for sure if your split is working, create a list and pass it to split, print the result. Then call split on the two lists created by split, and so on, to make sure what's happening. (Now would be a good time to use JUnit, but you can do that by "hand" if you want to).

If split works fine for the several cases you can think of, then call the merge routine with two lists, and analyze the result in the same fashion. If that works ok, then add some debugging output to your merge.

Basically, test each part of your algorithm independently, it'll me a lot faster to figure out the problem then looking at it as a whole.

Sorry for writing up a wall of text and still not answering the question, but this is how I would try to solve the problem.

answered Apr 11, 2012 at 10:45

pcalcao

16k1 gold badge49 silver badges65 bronze badges

3 Comments

John B Over a year ago

Unit tests RULE! Totally agree on using JUnit to help narrow scope of analysis.

user1280446 Over a year ago

Thanks for your reply. Just a quick question though - is there any difference in implementing the merge part iteratively rather than recursively besides being simpler? Time/space complexity perhaps?

pcalcao Over a year ago

Yes and no... the complexity will stay the same, but for very large lists, you'll be creating a huge stack of recursive calls, and there's a limit for that. Basically for each non-terminal recursive call, the JVM needs to add another context entry to the stack, when the recusive calls stop, they'll start getting solved until your method finally returns.

Collectives™ on Stack Overflow

Java - merge sort using linked list pointers

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