Ошибка в сортировке слиянием

Question

Я сделал собственную сортировку слиянием, в которой есть метод, который допускает только ArrayList и Comparator. Мой коллега просил, чтобы массив tmp, который я обычно объявлял в методе «слияния», был объявлен в первом методе-обертке (mergeSort). Теперь, если я выполню тест с 3 элементами, он не будет работать. Почему?

public static < T > void mergeSort(ArrayList < T > array, Comparator < T > c) {
    int high = array.size()-1;
    sort(array, c, 0, high, new ArrayList < T > (high + 1));
  }  

  protected static < T > void sort(ArrayList < T > array, Comparator < T > c, int low, int high, ArrayList < T > tmp) {
    if (low < high) {
      int mid = low + (high - low) / 2;
      sort(array, c, low, mid, tmp);
      sort(array, c, mid + 1, high, tmp);
      merge(array, c, low, mid, high, tmp);
    }
  }

  protected static < T > void merge(ArrayList < T > array, Comparator < T > c, int p, int mid, int q, ArrayList < T > tmp) {
    int i = p;
    int j = mid + 1;
    int k = 0;
    for (; i <= mid && j <= q; k++) {
      if (c.compare(array.get(i), array.get(j)) < 0)
        tmp.add(k, array.get(i++));
      else
        tmp.add(k, array.get(j++));
    }
    if (i <= mid && j > q) {
      while (i <= mid)
        tmp.add(k++, array.get(i++));
    } else {
      while (j <= q)
        tmp.add(k++, array.get(j++));
    }
    for (k = 0; k < tmp.size(); k++)
      array.set(k + p, tmp.get(k));
  }

Answer 1

Поскольку ваш tmp ArrayList ранее был локальным для метода merge, это означает, что после перемещения его в вызов mergeSort его следует очистить перед использованием в каждом вызове merge:

protected static < T > void merge(ArrayList < T > array, Comparator < T > c, int p, int mid, int q, ArrayList < T > tmp) {
    tmp.clear();
    ...
}

Не очищая его, вы будете добавлять к нему элементы при каждом вызове merge. Он будет только расти, и вы можете повторно использовать его устаревшие элементы.