Mergesort - Stackoverflow when splitting array not in a half

Question

I've a problem. I have to edit the standard mergesort algorithm, changing the ratio between the two halves of the array. Standard mergesort splits array in 2. BUT I've to split it with a coefficient.

Example:

I've a 10elements array, and i've to split it with a coeff of 0.2. This means that the first time the array is divided in 2 parts: one with 2 elements, the second with 8 elements. Being recursive, this ratio is applied every time I split the array.

The problem:

If the coeff >=0.5 no probs. If the ratio in <=0.5 every attempt leads to a stackoverflow.

Any help will be kindly appreciated!

Here the class:

public class Sort {
public static double coeff = 0.2;
public static void mergeSort(int[] a) {
    int vectorTemp[];
    vectorTemp = new int[a.length];
    mergeSort(a, vectorTemp, 0, a.length - 1);
}

private static void mergeSort(int[] a, int[] vectorTemp, int left, int right) {
    if (left < right) {
        int center = calculateMid(left, right);
        mergeSort(a, vectorTemp, left, center);
        mergeSort(a, vectorTemp, center + 1, right);
        merge(a, vectorTemp, left, center + 1, right);
    }
}

private static void merge(int[] a, int[] vectorAux, int posLeft, int posRight, int posEnd) {
    int endLeft = posRight - 1;
    int posAux = posLeft;
    int numElemen = posEnd - posLeft + 1;

    while (posLeft <= endLeft && posRight <= posEnd) {
        if ((a[ posLeft]) < (a[posRight])) {
            vectorAux[posAux++] = a[posLeft++];
        } else {
            vectorAux[posAux++] = a[posRight++];
        }
    }

    while (posLeft <= endLeft) {
        vectorAux[posAux++] = a[posLeft++];
    }

    while (posRight <= posEnd) {
        vectorAux[posAux++] = a[posRight++];
    }

    for (int i = 0; i < numElemen; i++, posEnd--) {
        a[posEnd] = vectorAux[posEnd];
    }
}
//this is the method i've added to calculate the size
private static int calculateMid(int left, int right){
    int mid = 0;
    int tot = right-left+1;
    int firstHalf = (int) (tot * coeff);
    mid = left + firstHalf;
    System.out.println(left+", "+mid +", "+firstHalf+", "+right + ", "+tot);

    return mid-1;
}

public static void main(String[] args) {
    int vector2[] = {10, 3, 15, 2, 1, 4, 9, 0};
    System.out.println("Array not ordered: " + Arrays.toString(vector2) + "\n");
    mergeSort(vector2);
    System.out.println("Array ordered: " + Arrays.toString(vector2));
}}

what is your stop-condition? stackoverflow means infinite recursion — Nikolay Kuznetsov
– Nikolay Kuznetsov, Commented Jan 24, 2013 at 16:55
code added, and to be honest I don't know which nonstop condition I've to add :/ And also WHY it works with coeff >=0.5 — ubi_v
– ubi_v, Commented Jan 24, 2013 at 17:04
For me the algorithmn looks alright except the calcMid Part. I think the error happens there. I'll do some furhter checks. Another question: Does it work with all kind of arrays(especiallay with odd numbers) — arnoapp
– arnoapp, Commented Jan 24, 2013 at 17:08

NPE · Accepted Answer · 2013-01-24 17:11:10Z

1

Here is a hint:

Think about what calculateMid() returns for a two-element array, and what happens in mergeSort() after that.

Once you figure out what happens there, it will also become clear why the code works for coeff >= 0.5.

edited Jan 24, 2013 at 17:11

answered Jan 24, 2013 at 17:03

NPE

503k114 gold badges970 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Mergesort - Stackoverflow when splitting array not in a half

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related