Сортировка слиянием создать кучи памяти

Question

Я написал эту сортировку слиянием, которая позволяет пользователю вызывать ее, передавая только два параметра (ArrayList и Comparator):

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/2));
  }  

  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) {
    tmp.clear();
    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()-p; k++)
      array.set(k + p, tmp.get(k));

  }
}

После вызова я попытался напечатать его содержимое (которое я должен был заказать):

Sorting.mergeSort(arrayA, new LongComparator());
System.out.println(Arrays.toString(arrayA.toArray()));

Но я получил эту ошибку:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:3332)
    at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:124)
    at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:448)
    at java.lang.StringBuilder.append(StringBuilder.java:136)
    at java.util.Arrays.toString(Arrays.java:4574)

Как мне улучшить сортировку слиянием? Является ли временный ArrayList основной причиной ошибки? Потому что эта ошибка происходит, когда я пытаюсь заказать миллионы данных. С 2-3 элементами это работает. РЕДАКТИРОВАТЬ: Это моя первая версия алгоритма, который не имеет метода поддержки только с двумя параметрами, которые мне нужно сделать

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

@SuppressWarnings("unchecked")
  public static <T> void merge(ArrayList<T> array, Comparator<T> c, int p, int mid, int q) {
    Object[] tmp = new Object[q-p+1]; 
    int i = p;
    int j = mid+1;
    int k = 0;
    while (i <= mid && j <= q) {
        if (c.compare(array.get(i), array.get(j))<0)
          tmp[k] = array.get(i++);
        else
          tmp[k] = array.get(j++);
        k++;
    }
    if (i <= mid && j > q) {
        while (i <= mid) 
          tmp[k++] = array.get(i++);
    } else {
        while (j <= q)
          tmp[k++] = array.get(j++);
    }
    for (k = 0; k < tmp.length; k++)
      array.set(k+p, (T)tmp[k]);
  }

Answer 1

Два способа решения проблемы:

Увеличение доступной памяти: Как было упомянуто Turing85, запустите java с большим объемом памяти, используя параметр VM, -Xmx2048m, например, для назначения 2 ГБ.

Уменьшение используемой памяти: При использовании ArrayList базовых типов, таких как Long и Double, в 4 раза (в моем простом эксперименте) используется больше памяти, чем при использовании эквивалентного массива базовых типов long / double.

ArrayList<Long> instead of long[]

также заставит код работать значительно медленнее по нескольким причинам (если вы собираетесь использовать сортировку слиянием для неосновных типов, вы можете увидеть увеличение производительности, но прирост памяти не будет столь значительным)