Java MergeSort - memory error: Java Heap Space

Question

I am trying to get some practice with sorting in Java.

Now I'm working on merge sorting ... Eclipse throws Out Of Memory Error: Java Heap space , but I'm not sure how to debug this.

I feel my code is ok - 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; } } 

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

Answer 2

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

it doesn’t come out because you don’t delete any items on the left or on the right, so you continue to add items to the sortedList until you run out of memory. You check if one of them is larger, but you never delete any elements, so the check will never return false, otherwise a loop.