java - 为什么合并排序需要花费太多时间来排序？

Question

我一直在尝试优化这个合并排序版本，但是对大约 300 万个寄存器进行排序需要太长时间。我哪里做错了？我希望得到一些帮助，谢谢。

Persona 是一个包含字符串和整数的类，以防万一你们想知道以帮助我。

public class Mergesort {
  private ArrayList<Persona> numbers = new ArrayList();
  private  ArrayList<Persona> helper;
  private int number;
  private boolean ascending;


  public void sort(ArrayList<Persona> values, boolean ascending) {
    this.numbers = values;
    this.ascending = ascending;
    number = values.size();
    helper = new ArrayList();
    mergesort(0, number - 1);
  }

  /**
   * Determines the middle of the array to sort the left side and the right side 
   * Then it merges both arrays.
   * @param low
   * @param high 
   */
  private void mergesort(int low, int high) {
    // check if low is smaller then high, if not then the array is sorted
    if (low < high) {
      // Get the index of the element which is in the middle
      int middle = low + (high - low) / 2;
      // Sort the left side of the array
      mergesort(low, middle);
      // Sort the right side of the array
      mergesort(middle + 1, high);
      // Combine them both
      merge(low, middle, high);
    }
  }

  /**
   * Merges the arrays.
   * @param low
   * @param middle
   * @param high 
   */
  private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
          helper.add(i, numbers.get(i));
    }

    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
      if ( helper.get(i).id  <= helper.get(j).id) {
        numbers.set(k, helper.get(i));
        i++;
      } else {
        numbers.set(k,helper.get(j));
        j++;
      }
      k++;
    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
      numbers.set(k,helper.get(i));
      k++;
      i++;
    }
  }}

Answer 1

你永远不会清除helper的内容(无论如何它不应该是全局的)，这意味着每次你合并越来越多的数据。我真的很惊讶你没有内存不足。