Stack overflow from a missed function call

I'm sorry if this is posted elsewhere (I can't find anything since my problem is pretty specific), but I understand (or at least theoretically) what the error is; I'm having trouble figuring out how to fix this. The code should show how merge sort works; The code works, but it never makes a call to the "merge" function (code below, I know it is bad practice to call everything in imports, but this is not a large project, so I don't care; just a preview, but it's written import java.util .; and imports java.security .;).

import java.util.*;
import java.security.*;

public class Merge {
    public static void mergeSort(int[] data) {
        sortArray(data, 0, data.length - 1);
    }

    private static void sortArray(int[] data, int low, int high) {
        if ((high - low) >= 1) {
            int m1 = low + high;
            int m2 = m1 + 1;

            System.out.printf("Split:  %s\n", subarrayString(data, low, high));
            System.out.printf("          %s\n", subarrayString(data, low, m1));
            System.out.printf("          %s\n\n", subarrayString(data, m2, high));

            sortArray(data, low, m1);
            sortArray(data, m2, high);

            merge(data, low, m1, m2, high);
        }
    }

    public static void merge(int[] data, int l, int m1, int m2, int r) {
        int lIndex = l, rIndex = r, cIndex = l, combined[] = new int[data.length];

        System.out.printf("Merge:  %s\n", subarrayString(data, l, m1));
        System.out.printf("             %s\n", subarrayString(data, m1, r));

        while (lIndex <= data[rIndex]) {
            if (data[lIndex] <= data[rIndex])
                combined[cIndex++] = data[lIndex++];
            else
                combined[cIndex++] = data[rIndex++];
        }

        if (lIndex == m2)
            while (rIndex <= r) combined[cIndex++] = data[rIndex++];
        else
            while (lIndex <= m1) combined[cIndex++] = data[rIndex++];
    }

    private static String subarrayString(int[] data, int low, int high) {
        StringBuilder temp = new StringBuilder();

        for (int i = 0; i < low; i++)
            temp.append("     ");

        for (int i = 0; i < high; i++)
            temp.append(" " + data[i]);

        return temp.toString();
    }

    public static void main2() {
        SecureRandom gen = new SecureRandom();

        int[] data = new int[10];

        for (int i = 0; i < data.length; i++) data[i] = 10 + gen.nextInt(50);

        System.out.printf("\nUnsorted Array:\n%s\n\n", Arrays.toString(data));
        mergeSort(data);
        System.out.printf("\nSorted Array:\n%s\n\n", Arrays.toString(data));
    }
}

      

Let me know if you need a driver file. To recap, the problem is that it never reaches the merge function call and results in an error.

+3


source to share


1 answer


A common cause is a bad recursive call. Typically, this is caused when your recursive functions do not have a correct termination condition. In your code, the 1st recursive call is always called with the same parameter 0 and (length - 1) and no interruption, and it will get stuck in an infinite loop. Correct your code and update the value of m1 to terminate.

Consider array length 6:



low = 0 and high = 5
 m1 = 5
sortArray(data, 0, 5);

      

+2


source







All Articles