Merge Sort Implementation java

Question

I'm trying to implement my own Mergesort function but am having a hard time figuring out what's not working.

The output I get for UnSorted: [6, 1, 2, 7, 2, 3, 9, 7, 6] is Sorted: [2, 3, 6, 1, 2, 7]

Here's what I have so far:

public class mergeSort {

    public static void main(String[] args) {
        List<Integer> l = new ArrayList<Integer>();
        Random rd = new Random();

        for (int i = 1; i < 10; i++) {
            l.add(rd.nextInt(10) + 1);
        }   

        System.out.println("UnSorted: " + l);
        msort(l);
        System.out.println("Sorted: "+msort(l));
    }

    public static List<Integer> msort(List<Integer> l) {     
        if (l.size() <= 1) {
            return l;
        }

        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();

        for (int i = 0; i < (l.size() / 2); i++) {
            left.add(l.get(i));
        }
        for (int i = l.size() / 2; i < l.size(); i++) {
            right.add(l.get(i));
        }

        msort(left);
        msort(right);
        //System.out.println(left + "" +right);

        return join(left,right);
    }

    public static List<Integer> join(List<Integer> left, List<Integer> right) { 
        /*if (right.size() == 0) {
            return left;
        }
        if (left.size() == 0) {
            return right;
        }*/

        List<Integer> fin = new ArrayList<Integer>();
        // pointers
        int lp = 0, rp = 0, fp = 0;

        while (lp < left.size() && rp < right.size()) { 
            if (left.get(lp) < right.get(rp)) {
                fin.add(left.get(lp));  
                lp++;
            } else {
                fin.add(right.get(rp));  
                rp++;        
            }
            fp++;
        }   
        return fin;
    }       
}

Sanjeev · Accepted Answer · 2014-02-21 15:05:47Z

2

There are couple of problems with your code. Your approach is right though

In join method you are leaving some of the elements in list because of your while loop is using

lp < left.size() && rp < right.size()

which will loop until one of the lists have been added to the fin and there might still be some element left in other list. so you need two more loops to accommodate this:
```
while(lp < left.size()) {
    fin.add(left.get(lp++));
}
while(rp < right.size()) {

    fin.add(right.get(rp++));
}
```
there is problem in your msort method as well you are not using the return values from msort so you need this:

left = msort(left);

right = msort(right);

Hope this helps.

answered Feb 21, 2014 at 15:05

Sanjeev

9,9762 gold badges24 silver badges33 bronze badges

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

2 Comments

Destruktor Over a year ago

I think that this was the purpose of fp, but it is not implemented anywhere in the logic (fp is incremented in every loop, but never tested)

Sanjeev Over a year ago

Your Welcome @rohstar .. have fun coding :)

Community · Accepted Answer · 2017-05-23 11:57:47Z

You're returning the sorted list in msort method but never assigning this value anywhere in your code. A possible solution might be reassigning both your left and right after sorting them:

public static List<Integer> msort(List<Integer> l){
    if (l.size() <= 1) {
        return l;
    }
    List<Integer> left = new ArrayList<Integer>();
    List<Integer> right = new ArrayList<Integer>();
    for(int i = 0; i <(l.size()/2);i++){
        left.add(l.get(i));
    }
    for(int i = l.size()/2; i <l.size();i++){
        right.add(l.get(i));
    }
    //this is where you should assign them
    left = msort(left);
    right = msort(right);
    //System.out.println(left + "" +right);
    return join(left,right);
}

Similar when calling msort in main method:

l = msort(l);

As noted by @Sanjeev, you're also missing array elements in join method. Use that piece of code to fix it (taken it from his/her answer):

while (lp < left.size() && rp < right.size()) {
    //logic inside this while loop...
}
//add this code
while(lp < left.size()) {
    fin.add(left.get(lp++));
}
while(rp < right.size()) {
    fin.add(right.get(rp++));
}
return fin;

Apart of this, you should avoid using List#get method since depending on the class implementation may take O(n) time e.g. LinkedList, instead use Iterator as shown here.

MTilsted · Accepted Answer · 2014-02-21 14:55:56Z

0

One obvious problem is that your merge method returns a sorted list. It does not modify its own intput list. This is not in itself a prbolem, but it mean that your call: msort(l);

does not change l, but does instead return a sorted list. So you should do

List sortedList=msort(l); and then try to print that sorted list.

answered Feb 21, 2014 at 14:55

MTilsted

5,5359 gold badges50 silver badges88 bronze badges

1 Comment

turbo Over a year ago

not sure this will solve the problem, but definitely a step in the right direction

Collectives™ on Stack Overflow

Merge Sort Implementation java

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related