CODEWITHSUNDEEP
javasortingmergesort
93zone
93zone

Reputation: 11

What's wrong in this "mergeSort"?

There's a mergeSort code that I copied at class lesson, can you help me to find the errors?

When I run the main that use mergeSort the program enters in an infinite loop but doesn't display any error. I tried to run in debug mode but I am not very expert and I don't find what's wrong. However I think that the error is in mergeSort(int[] v, int inf, int sup) recursion.

public class CopyOfSortMethods {

private static void merge(int[] v, int inf, int med, int sup) {
    int aux[] = new int[v.length];
    int i = inf;
    int j = med + 1;
    int k = inf;

    while ((i <= med) && (j <= sup)) {
        if (v[i] < v[j]) {
            aux[k] = v[i];
            i++;
            k++;
        } else {
            aux[k] = v[j];
            j++;
            k++;
        }
    }
    while (i <= med) {
        aux[k] = v[i];
        i++;
        k++;
    }
    while (j <= sup) {
        aux[k] = v[j];
        j++;
        k++;
    }
    for (i = 0; i <= sup; i++) {
        v[i] = aux[i];
    }
}

public static void mergeSort(int[] v, int inf, int sup) {
    int med;

    while (inf < sup){
        med = (inf + sup)/2;
        mergeSort(v, inf, med);
        mergeSort(v, med + 1, sup);
        merge(v, inf, med, sup);
    }
}

public static void mergeSort(int[] v) {
    if(v!=null) {
        mergeSort(v, 0, v.length - 1);
    }

}
}

Upvotes: 0

Views: 109

Answers (2)

Luiggi Mendoza
Luiggi Mendoza

Reputation: 85779

The problems in your merge sort (based in the comments):

  1. In mergeSort method, you're recursively calling the mergeSort inside a while loop and never changing the values of inf and sup. Change this for an if instead.

     if (inf < sup) {
     //code goes here...
 }

  2. In your merge sort, at the bottom of the method body, you're moving the items all the items from aux array to v array. You should only move the elements between inf and sup:

    //for (i = 0; i <= sup; i++) {
for (i = inf; i <= sup; i++) {
    //code goes here...
}

Upvotes: 0

pamphlet
pamphlet

Reputation: 2104

As Maverik points out, the issue is the while loop in mergeSort().

inf and sup are never modified, so inf is always less than sup. The loop never terminates.

Upvotes: 1

Related Questions