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;
    }       
}

Answer 1

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

1. 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++));
   }
   

2. 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.

Answer 2

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.

Answer 3

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.