Using Merge Sort on ArrayList and LinkedList : Java

Question

I need to sort a list of 1000 ints with a merge sort; from what I can tell, my algorithm looks like it should work, but when I print out the 'sorted' list, it's still not sorted. I'm really stumped, and I was wondering if anybody could point me in the right direction. Here's my code:

package edu.neumont.csc250;

import java.util.Random;

import edu.neumont.csc250.LinkedList.Node;


public class Tester {

    ArrayList<Integer> arrayList1000;
    ArrayList<Integer> arrayList10000;
    ArrayList<Integer> arrayList100000;

    LinkedList<Integer> linkedList1000;
    LinkedList<Integer> linkedList10000;
    LinkedList<Integer> linkedList100000;

    public Tester(){}

    public void createLists(){
        arrayList1000 = new ArrayList<Integer>();
        arrayList1000 = populateRandoms(arrayList1000, 1000);
        arrayList10000 = new ArrayList<Integer>();
        arrayList10000 = populateRandoms(arrayList10000, 10000);
        arrayList100000 = new ArrayList<Integer>();
        arrayList100000 = populateRandoms(arrayList100000, 100000);

        linkedList1000 = new LinkedList<Integer>();
        linkedList1000 = populateRandoms(linkedList1000, 1000);
        linkedList10000 = new LinkedList<Integer>();
        linkedList10000 = populateRandoms(linkedList10000, 10000);
        linkedList100000 = new LinkedList<Integer>();
        linkedList100000 = populateRandoms(linkedList100000, 100000);
    }

    public ArrayList<Integer> populateRandoms(ArrayList<Integer> list, int size){
        Random r = new Random();

        for(int i = 0; i < size; i++){
            list.add(r.nextInt(1000) + 1);
            //System.out.println(list.get(i));
        }
        return list;
    }

    public LinkedList<Integer> populateRandoms(LinkedList<Integer> list, int size){
        Random r = new Random();

        for(int i = 0; i < size; i++){
            list.add(r.nextInt(1000) + 1);
            //System.out.println(list.get(i));
        }
        return list;
    }

    public void arraySearches(){
        System.out.println("STARTING SEARCH OF 1000 INTEGERS...");

        long startTime = System.nanoTime();
        long endTime;
        try {
            System.out.println(sequentialSearch(arrayList1000, 123));
            if(sequentialSearch(arrayList1000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(arrayList1000.get(sequentialSearch(arrayList1000, 123)));
            }
        } finally {
            endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("1000 elements takes " + (duration/1000000000) + " seconds, " +
                (duration%1000000000)/1000000+ " milliseconds, " + (duration%1000000000)%1000000 +
                " nanoseconds to search a CustomArrayList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 10000 INTEGERS...");

        long startTime2 = System.nanoTime();
        long endTime2;
        try {
            System.out.println(sequentialSearch(arrayList10000, 123));
            if(sequentialSearch(arrayList10000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(arrayList10000.get(sequentialSearch(arrayList10000, 123)));
            }
        } finally {
            endTime2 = System.nanoTime();
            long duration2 = endTime2 - startTime2;
            System.out.println("10000 elements takes " + (duration2/1000000000) + " seconds, " +
                (duration2%1000000000)/1000000+ " milliseconds, " + (duration2%1000000000)%1000000 +
                " nanoseconds to search a CustomArrayList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 100000 INTEGERS...");

        long startTime3 = System.nanoTime();
        long endTime3;
        try {
            System.out.println(sequentialSearch(arrayList100000, 123));
            if(sequentialSearch(arrayList100000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(arrayList100000.get(sequentialSearch(arrayList100000, 123)));
            }
        } finally {
          endTime3 = System.nanoTime();
            long duration3 = endTime3 - startTime3;
            System.out.println("100000 elements takes " + (duration3/1000000000) + " seconds, " +
                (duration3%1000000000)/1000000+ " milliseconds, " + (duration3%1000000000)%1000000 +
                " nanoseconds to search a CustomArrayList with a sequential search.");
        }
    }

    public void linkedSearches(){
        System.out.println("STARTING SEARCH OF 1000 INTEGERS...");

        long startTime = System.nanoTime();
        long endTime;
        try{
            System.out.println(sequentialSearch(linkedList1000, 123));
            if(sequentialSearch(linkedList1000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(linkedList1000.get(sequentialSearch(linkedList1000, 123)));
            }
        } finally {
            endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("1000 elements takes " + (duration/1000000000) + " seconds, " +
                (duration%1000000000)/1000000+ " milliseconds, " + (duration%1000000000)%1000000 +
                " nanoseconds to search a CustomLinkedList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 10000 INTEGERS...");

        long startTime2 = System.nanoTime();
        long endTime2;
        try{
            System.out.println(sequentialSearch(linkedList10000, 123));
            if(sequentialSearch(linkedList10000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(linkedList10000.get(sequentialSearch(linkedList10000, 123)));
            }
        } finally {
            endTime2 = System.nanoTime();
            long duration2 = endTime2 - startTime2;
            System.out.println("10000 elements takes " + (duration2/1000000000) + " seconds, " +
                (duration2%1000000000)/1000000+ " milliseconds, " + (duration2%1000000000)%1000000 +
                " nanoseconds to search a CustomLinkedList with a sequential search.");
        }


        System.out.println("STARTING SEARCH OF 100000 INTEGERS...");

        long startTime3 = System.nanoTime();
        long endTime3;
        try{
            System.out.println(sequentialSearch(linkedList100000, 123));
            if(sequentialSearch(linkedList100000, 123) == -1){
                System.out.println("Not found in the list.");
            }
            else{
                //System.out.println(linkedList100000.get(sequentialSearch(linkedList100000, 123)));
            }
        } finally {
            endTime3 = System.nanoTime();
            long duration3 = endTime3 - startTime3;
            System.out.println("100000 elements takes " + (duration3/1000000000) + " seconds, " +
                (duration3%1000000000)/1000000+ " milliseconds, " + (duration3%1000000000)%1000000 +
                " nanoseconds to search a CustomLinkedList with a sequential search.");
        }
    }

    public void arraySorts(){
        arrayList1000 = mergeSort(arrayList1000);
        for(int i = 0; i<1000; i++){
            System.out.println(arrayList1000.get(i));
        }
    }

    public void linkedSorts(){
//      linkedList1000 = mergeSort(linkedList1000);
//      for(int i = 0; i<1000; i++){
//          System.out.println(arrayList1000.get(i));
//      }
    }

    public ArrayList<Integer> mergeSort(ArrayList<Integer> list){
        ArrayList<Integer> first = new ArrayList<Integer>();
        ArrayList<Integer> second = new ArrayList<Integer>();
        ArrayList<Integer> sortedList = null;

        System.out.println("MERGE SORTING...");
        if(list.size() > 1){
            for(int i = 0; i<(list.size()/2); i++){
                first.add(list.get(i));
            }
            for(int j = list.size()/2; j<list.size(); j++){
                second.add(list.get(j));
            }
            mergeSort(first);
            mergeSort(second);
        }
        sortedList = merge(first, second);


        return sortedList;
    }

    public ArrayList<Integer> merge(ArrayList<Integer> first, ArrayList<Integer> second){
        ArrayList<Integer> newList = new ArrayList<Integer>();

        int i = 0;
        int j = 0;

        while(i<first.size() && j<second.size()){
            if(first.get(i) <= second.get(j)){
                newList.add(first.get(i));
                i++;
            }
            else{
                newList.add(second.get(j));
                j++;
            }
        }
        if(i==first.size()){
            for(int k = j; k<second.size(); k++){
                newList.add(second.get(k));
            }
        }
        else{
            for(int l = i; l<first.size(); l++){
                newList.add(first.get(l));
            }
        }
//      while(i<first.size()){
//          for(int i : first){
//              
//          }
//          newList.add()
//      }
//      while(j<second.size()){
//          
//      }

        return newList;
    }

    public List<Integer> mergeSort(LinkedList<Integer> list){
        return list;
    }

    public int sequentialSearch(ArrayList<Integer> list, int key){
        for(int i = 0; i < list.size()-1; i++){
            if(list.get(i).equals(key)){
                return i;
            }
        }
        return -1;
    }

    public int sequentialSearch(LinkedList<Integer> list, int key){
        Node current = list.head;
        for(int i = 0; i < list.size()-1; i++){
            if(current.content.equals(key)){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Tester t = new Tester();
        t.createLists();
        //t.arraySearches();
        //t.linkedSearches();
        t.arraySorts();
        //t.linkedSorts();
    }
}

first of all, you might want to boil that example down to the part that's actually being used. having said that; your code does actually seem to be doing the right thing. at this point, you might want to add debug outputs, like, which method is called at which point with which parameters, which elements are being joint, what are the return values. — Nicolas78
– Nicolas78, Commented May 4, 2011 at 16:21
The solution is a combination of the answers by @proactif and @Milan — Vincent Ramdhanie
– Vincent Ramdhanie, Commented May 4, 2011 at 16:33

proactif · Accepted Answer · 2011-05-04 16:26:55Z

2

I think you should replace

mergeSort(first);
mergeSort(second);

by

first = mergeSort(first);
second = mergeSort(second);

answered May 4, 2011 at 16:26

proactif

11.8k1 gold badge20 silver badges12 bronze badges

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

2 Comments

Chris V. Over a year ago

I just tried this and it causes an illegalargumentexception to be thrown when I try to print out each element of the (newly) sorted list.

Peter Lawrey Over a year ago

@ChrisV, That because the mergeSort is producing an empty list and you assume there is 1000 elements. I have a fix for the second bug in my answer.

Jordan · Accepted Answer · 2011-05-04 16:10:12Z

1

your mergeSort function doesn't do anything except return the list.

public List mergeSort(LinkedList list) {
    return list;
}

How do you expect it to sort?

answered May 4, 2011 at 16:10

Jordan

5,0584 gold badges29 silver badges39 bronze badges

2 Comments

Chris V. Over a year ago

You're looking at the wrong one. There's two methods, one for a linked list and one for an array list. I've only done the arrayList one so far.

Jordan Over a year ago

I will check that code too, but as per your question you said you were trying to sort a "list"

Milan · Accepted Answer · 2011-05-04 16:23:13Z

1

In mergeSort(ArrayList<Integer> list) when the list contains only 1 element, you ignore it and try to merge first and second arraylist which are empty.

If you check the size of the returned sorted arraylist, you should notice that it probably is missing some elements.

answered May 4, 2011 at 16:23

Milan

15.9k20 gold badges60 silver badges65 bronze badges

Comments

Peter Lawrey · Accepted Answer · 2011-05-04 16:34:42Z

0

I stepped through you code with a debugger and found one bug.

first = mergeSort(first);
second = mergeSort(second);

after that you have an issue there you need to handle one element correctly.

public ArrayList<Integer> mergeSort(ArrayList<Integer> list) {
    System.out.println("MERGE SORTING...");
    if (list.size() < 2)
        return new ArrayList<Integer>(list);

    ArrayList<Integer> first = new ArrayList<Integer>(list.subList(0, list.size() / 2));
    ArrayList<Integer> second = new ArrayList<Integer>(list.subList(list.size()/2, list.size()));

    return merge(mergeSort(first), mergeSort(second));
}

edited May 4, 2011 at 16:34

answered May 4, 2011 at 16:28

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

6 Comments

Chris V. Over a year ago

I'm assuming that previously the code was without the first= and second= ??

Peter Lawrey Over a year ago

@ChrisV, perhaps you should ask the person who write the code originally. ;)

Chris V. Over a year ago

Makes sense, but just FYI I'm using custom collections classes (custom arraylist and custom linkedlist), so I dont have any constructors that take in the parameters you mentioned.

Chris V. Over a year ago

I'm also a little confused by the fact that you seem to have unreachable code...once you get to the case where list.size() is 1 and return newArrayList<Integer> wont that cut off the method before you reach the 'return merge(mergeSort(first,mergeSortsecond)) part? EDIT: nevermind, I see how it works now; I was just thrown off by the lack of brackets enclosing your if statement

Peter Lawrey Over a year ago

You can copy them the way you have. When you have one element it will be in the second list. ;)

|

Collectives™ on Stack Overflow

Using Merge Sort on ArrayList and LinkedList : Java

4 Answers 4

2 Comments

2 Comments

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related