Analyzing An ArrayList Merge Method
The mergeSort and merge methods below are used to sort an ArrayList of integers. Which statement describes a potential pitfall of the merge method’s implementation?
public static void mergeSort(ArrayList<Integer> list) {
if (list.size() <= 1) return;
int mid = list.size() / 2;
ArrayList<Integer> left = new ArrayList<Integer>(list.subList(0, mid));
ArrayList<Integer> right = new ArrayList<Integer>(list.subList(mid, list.size()));
mergeSort(left);
mergeSort(right);
merge(list, left, right);
}
public static void merge(ArrayList<Integer> list, ArrayList<Integer> left, ArrayList<Integer> right) {
int i = 0, j = 0, k = 0;
while (i < left.size() && j < right.size()) {
if(left.get(i) < right.get(j)) {
list.set(k++, left.get(i++));
} else {
list.set(k++, right.get(j++));
}
}
while (i < left.size()) {
list.set(k++, left.get(i++));
}
while (j < right.size()) {
list.set(k++, right.get(j++));
}
}
A
The merge function lacks a recursive call, causing an infinite loop.
B
The merge function incorrectly uses add() instead of set(), causing duplicate entries.
C
The merge function assumes that the original list is preallocated and does not require resizing, which can lead to index errors if it isn’t.
D
The merge function does not check for null elements before comparing, leading to NullPointerExceptions.
Question Leaderboard
Not enough data yet to show leaderboard.
APFIVE