CODEWITHSUNDEEP
javasorting
Ranguro
Ranguro

Reputation: 27

Why is the merge-sort taking too much time to sort?

I've been trying to optimize this mergesort version but it takes too long to sort around 3 million of registers. Where am I doing it wrong? I would appreciate some help, thanks.

Persona is a class that has a string and an Integer, just in case that you guys want to know in order to help me. 

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

Upvotes: 0

Views: 363

Answers (2)

Arpan Mukherjee
Arpan Mukherjee

Reputation: 3

Is your code running and the o/p is alryt? In the merge function there must be another loop,after the first while loop. The first while loop terminated because either j>high or i>middle. You just wrote j>high condition,dere is no i>middle condtn.After that loop thre must be something like dis

if(j>high)
{
while (i <= middle) {
      numbers.set(k,helper.get(i));
      k++;
      i++;
    }
}
else
{
while (j <= high) {
      numbers.set(k,helper.get(j));
      k++;
      j++;
    }
}

N clear the helper

Upvotes: 0

Jim Garrison
Jim Garrison

Reputation: 86764

You never clear out the contents of helper (which should not be a global anyawy), which means each time you are merging more and more data. I'm really surprised you didn't get out-of-memory.

Upvotes: 4

Related Questions