1

I'm trying to get some practice with sorting in Java.

I'm working on the merge sort now... Eclipse is outputting Out Of Memory Error: Java Heap space, but I'm not sure how to debug that.

I feel like my code is okay- any thoughts?

import java.util.ArrayList;
import java.util.List;
public class Sorts {
    List<Integer> initialList;

    public Sorts() {
        initialList = new ArrayList<Integer>();
        initialList.add(2);
        initialList.add(5);
        initialList.add(9);
        initialList.add(3);
        initialList.add(6);

        System.out.print("List: [");
        for (int values : initialList) {
            System.out.print(values);
        }
        System.out.println("]");

        splitList(initialList);
    }

    public List<Integer> splitList(List<Integer> splitMe)   {
        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();

        if (splitMe.size() <= 1) {
            return splitMe;
        }

        int middle = splitMe.size()/2;
        int i = 0;
        for (int x: splitMe) {
            if (i < middle) {
                left.add(x);
            }
            else {
                right.add(x);
            }
            i++;
        }
        left = splitList(left);
        right = splitList(right);

        return mergeThem(left, right);
    }

    public List<Integer> mergeThem(List<Integer> left, List<Integer> right) {
        List<Integer> sortedList = new ArrayList<Integer>();
        int x = 0;
        while (left.size() > 0 || right.size() > 0) {
            if (left.size() > 0 && right.size() > 0) {
                if (left.get(x) > right.get(x)) 
                    sortedList.add(left.get(x));
                else 
                    sortedList.add(right.get(x));
            }
            else if (left.size() > 0) {
                sortedList.add(left.get(x));
            }
            else if (right.size() > 0) {
                sortedList.add(right.get(x));
            }
        }
        return sortedList;
    }   
}
Improve this question
11
  • 1
    I'd hazard a guess the code is infinitely adding items to the list until there's no more memory. Step through your code with a debugger to see if that's true. Commented Mar 22, 2013 at 20:37
  • If you're getting OOME's on input that small, you've probably got infinite recursion. Commented Mar 22, 2013 at 20:37
  • try visualvm.exe, it's in the bin-folder of the JDK. google for an tutorial. Commented Mar 22, 2013 at 20:37
  • 3
    The flaws are described in your last question: stackoverflow.com/q/15563557/1065197. By the way, the error is in your mergeThem method where you keep adding elements in sortedList indefinitely. Commented Mar 22, 2013 at 20:38
  • 1
    It's a way to say remove the first element of left array that you haven't done. But don't try to follow the algorithm to the letter, instead I recommend you to see the animation and get your own idea. Commented Mar 22, 2013 at 20:47

2 Answers 2

Reset to default
1

Providing a possible implementation of the mergeThem method using Java elements:

public List<Integer> mergeThem(List<Integer> left, List<Integer> right) {
    //set the sorted list
    List<Integer> sortedList = new ArrayList<Integer>();
    //getting the iterators for both lists because List#get(x) can be O(N) on LinkedList
    Iterator<Integer> itLeft = left.iterator();
    Iterator<Integer> itRight = right.iterator();
    //getting flags in order to understand if the iterator moved
    boolean leftChange = true, rightChange = true;
    //getting the current element in each list
    Integer leftElement = null, rightElement = null;
    //while there are elements in both lists
    //this while loop will stop when one of the list will be fully read
    //so the elements in the other list (let's call it X) must be inserted
    while (itLeft.hasNext() && itRight.hasNext()) {
        //if left list element was added to sortedList, its iterator must advance one step
        if (leftChange) {
            leftElement = itLeft.next();
        }
        //if right list element was added to sortedList, its iterator must advance one step
        if (rightChange) {
            rightElement = itRight.next();
        }
        //cleaning the change flags
        leftChange = false;
        rightChange = false;
        //doing the comparison in order to know which element will be inserted in sortedList
        if (leftElement <= rightElement) {
            //if leftElement is added, activate its flag
            leftChange = true;
            sortedList.add(leftElement);
        } else {
            rightChange = true;
            sortedList.add(rightElement);
        }
    }
    //this is the hardest part to understand of this implementation
    //java.util.Iterator#next gives the current element and advance the iterator on one step
    //if you do itLeft.next then you lost an element of the list, that's why we have leftElement to keep the track of the current element of left list (similar for right list)
    if (leftChange && rightElement != null) {
        sortedList.add(rightElement);
    }
    if (rightChange && leftElement != null) {
        sortedList.add(leftElement);
    }
    //in the end, you should add the elements of the X list (see last while comments).
    while (itLeft.hasNext()) {
        sortedList.add(itLeft.next());
    }
    while (itRight.hasNext()) {
        sortedList.add(itRight.next());
    }
    return sortedList;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0 
while (left.size() > 0 || right.size() > 0) {

doesn't exit because you don't remove any items from your left or right, so you keep adding items to sortedList until it runs out of memory. You check if either of them is greater than 0 but you never remove any items so the check will never return false, aka infinite loop.

Improve this answer

2 Comments

you also never increment x that's not the reason of the error. The error is that both left and right lists size never decrease.
I shouldn't be incrementing x because the index always need to point to 0... the first element in the list which needs to be compared against

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.