Merge sort with array lists in java

Question

So for homework I have to write a program that mergeSorts with array lists from a code that works with regular arrays, I was just wondering if someone could help me figure out where I went wrong, because my code throws a ton of NULL POINTER exceptions, and I have tried to fix them, but when I fix one it goes to another...and so on....

Thanks! My code:

private static ArrayList<Integer> numbers= new ArrayList<Integer>();
private static ArrayList<Integer> helper;
private static int number;
public static void sort(ArrayList<Integer> myNumbers){
    for(int i=0; i<myNumbers.size();i++){
        numbers.add(myNumbers.get(i));
    }
    //numbers=myNumbers;
    number = myNumbers.size()-1;

    mergesort(0, number -1);
}
private static void mergesort(int low, int high){
    //check if low is smaller than high, if not then the array is sorted
    if(low<high){
        //get the index of the element which is in the middle
        int middle=low+(high-low)/2;
        //sort the left side of the array
        mergesort(low, middle);
        //sort the right side of the array
        mergesort(middle +1, high);
        //combine them both
        merge(low, middle, high);
    }
}
private static void merge(int low, int middle, int high){
    //copy both parts into the helper array
    for(int i=high;i>low;i++){
        helper.add((numbers.get(i)));
    }

    int i=low;
    int j=middle+1;
    int k=low;
    //copy the smallest myNumbers from either the left or right side back to the original array
    while(i<middle  && j<high){
        if(helper.get(i)< helper.get(j)){
            numbers.set(k,(helper.get(i)));
            i++;
        }
        else{
            numbers.set(k,(helper.get(j)));
            j++;
        }
        k++;
    }
    //copy the rest of the left side of the array into target array
    while(i<middle){
        numbers.set(k,helper.get(i));
        k++;
        i++;
    }
}

Returns:

Exception in thread "main" java.lang.NullPointerException
at BinarySearch.merge(BinarySearch.java:61)
at BinarySearch.mergesort(BinarySearch.java:55)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.mergesort(BinarySearch.java:51)
at BinarySearch.sort(BinarySearch.java:43)
at BinarySearch.main(BinarySearch.java:25)

Your helper is not initialized. That's causing you trouble — Rodrigo Sasaki
– Rodrigo Sasaki, Commented Apr 25, 2013 at 12:08

collapsar · Accepted Answer · 2013-04-25 12:09:50Z

1

here's the culprit:

for(int i=high;i>low;i++){
    helper.add((numbers.get(i)));
}

use for(int i=high; i>=low; i--) { instead.

answered Apr 25, 2013 at 12:09

collapsar

17.4k5 gold badges40 silver badges66 bronze badges

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

Comments

blackuprise · Accepted Answer · 2013-04-25 12:18:58Z

1

It tries to access helper field in merge function which is not created.

Also I think you should remove static keyword from all functions/fields.

private static ArrayList helper;

to

private static ArrayList helper= new ArrayList();

edited Apr 25, 2013 at 12:18

answered Apr 25, 2013 at 12:05

blackuprise

4506 silver badges26 bronze badges

2 Comments

user2319595 Over a year ago

I can't remove static because it is in the same class as my main

blackuprise Over a year ago

if you try to run it multiple times, numbers and helper will have previous values so you would need to clear list before running it again, also best way is to move this functionality to a new class MergeSort and in main class create new instance of MergeSort and call desired functions.

Kent · Accepted Answer · 2013-04-25 12:19:10Z

0

blackuprise pointed out your two problems.

Your merge implementation has another problem, which could make your merge result wrong. At the end of your merge method, you have:

//copy the rest of the left side of the array into target array
while...

how can you so sure every time all right side of the array would be merged, and only left part has elements left? (strange sentence ^_^ left part has sth. left.)

You should check for the right side too. or use a SENTINEL to avoid the "rest" checking.

answered Apr 25, 2013 at 12:19

Kent

197k36 gold badges248 silver badges317 bronze badges

5 Comments

user2319595 Over a year ago

Not sure what you mean, I haven't taken java that long.

Kent Over a year ago

@user2319595 the merge method will merge two sub-arrays. if you are lucky, after your first while the two sub-arrays have no elements left. however either of them could have elements left. you have to handle the rest elements, add them to your target/merged array. You just checked the left side, you didn't check the right side. take a look this code, I had two merge methods, with or without sentinel: github.com/sk1418/jalgorithm/blob/master/src/main/java/com/kent/…

Kent Over a year ago

@user2319595 it depends on the input array. As I said, if you are lucky, your mergesort will give correct result. but not always. :) make some test cases, you will see.

user2319595 Over a year ago

haha thanks! Yea, i have a program that puts 100 random ints in a text file and turns that into an arraylist for my tester

user2319595 Over a year ago

But right now it is returning a bunch of zeroes and the number 26 about 12 times then 45 and stopping

Belkacem REBBOUH · Accepted Answer · 2013-04-25 12:22:33Z

0

If you are trying to achieve a merge sort using your algorithm for an academic use that the given answer was a good one, else if you are interested in an implementation that Guava already has, then here it is: guava Iterators

answered Apr 25, 2013 at 12:22

Belkacem REBBOUH

5593 silver badges6 bronze badges

Comments

Paulina Voicu · Accepted Answer · 2015-07-17 21:25:23Z

public class Merged

public  static void sort(List<String>result )
{

     for( i=0;i<result.size();i++)
     {
        try{

          try{


         if(result.get(i).compareTo(result.get(i+1))>0)
             {
             String aux=result.get(i);
             result.set(i, result.get(i+1));
             result.set(i+1, aux);

             }


             }catch(NullPointerException e){}
          }catch(ClassCastException z){}

        }
    }


public static void main(String[]args) throws ClassNotFoundException
{ 
    String[]resultentry=new String[100];
    int index;//nr de elemente din vectorul de stringuri//
    int i;

    try{
   //declare files and lists//
    BufferedReader firstfile;
    BufferedReader secondfile;


    firstfile=new BufferedReader(new FileReader("lista1.txt"));
    secondfile=new BufferedReader(new FileReader("lista2.txt"));;


         firstentry=firstfile.readLine();
        secondentry=secondfile.readLine();

        while(firstentry!=null&&secondentry!=null)
        {
        firstlist.add(firstentry);
        firstentry=firstfile.readLine();

        secondlist.add(secondentry) ;
        secondentry=secondfile.readLine();

         }


     }catch(IOException exp){}


     try{

    java.util.Collections.sort(firstlist);
    System.out.println("First list sorted :"+ firstlist);

    java.util.Collections.sort(secondlist);
    System.out.println("Second list sorted"+secondlist);


    firstlist.addAll(secondlist);
    java.util.Collections.sort(firstlist);

    System.out.println("Result  list sorted "+" "+firstlist);

    }catch(ClassCastException b){}

   }

}`

Collectives™ on Stack Overflow

Merge sort with array lists in java

5 Answers 5

Comments

2 Comments

5 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

2 Comments

5 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related