What's wrong with my Merge sort java code?

Question

This is my java code.

public static int[] merge_sort(int[] arr, int p, int r) {
    if (p < r) {
        int q = p + r / 2;

        merge_sort(arr, p, q);
        merge_sort(arr, q + 1, r);
        merge(arr, p, q, r);
    }

    return arr;
}

public static void merge(int[] arr, int p, int q, int r) {
    int i = p;
    int j = q + 1;

    int[] tempArr = new int[arr.length];
    System.out.println(tempArr.length);

    int k = p;

    while (i <= q && j <= r) {
        if (arr[i] <= arr[j]) {
            tempArr[k] = arr[i];
            i++;
        } else {
            tempArr[k] = arr[j];
            j++;
        }

        k++;
    }

    while (i <= q) {
        tempArr[k] = arr[i];
        i++;
        k++;
    } 

    while (j <= r) {
        tempArr[k] = arr[j];
        j++;
        k++;
    }

    for (int h = p; h <= r; h++) {
        arr[h] = tempArr[h];
    }
}

And my test code is here.

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] testArr = {3, 5, 1, 9, 2};
    int[] sortedArr = merge_sort(testArr, 0, testArr.length - 1);

    for (int num: sortedArr) {
        System.out.print(num);
    }
}

When I tested with my test code, 'java.lang.StackOverflowError' error was called. Error is occurred in 'merge_sort(arr, p, q);' line. I don't know why this error occurred. What's wrong with my code?

[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Andy Turner, Mar 06 '18 at 14:12
I solved it. int q = p + r / 2; This line is wrong. This code should be (p+r) / 2 ... It's my silly mistake. — Alpaca, Mar 06 '18 at 14:22
Good job solving it. Submit the solution as an Answer, and then mark it as the correct answer. — baileyrt, Mar 06 '18 at 14:26

score 0 · Answer 1 · answered Mar 06 '18 at 14:21

0

You have an endless recursive call in your code:

 merge_sort(arr, p, q); // this one calls the same method over and over again
 merge_sort(arr, q + 1, r);
 merge(arr, p, q, r);

The first call is missing the fourth parameter

answered Mar 06 '18 at 14:21

Emerson Cod

1,990
3
21
39

I don't understand meaning of the fourth parameter. What do I need? – Alpaca Mar 06 '18 at 14:25
i dont know merge sort to answer that - I assume you know what you are writing, so this is on your table – Emerson Cod Mar 06 '18 at 18:44

score 0 · Accepted Answer · answered Mar 06 '18 at 14:25

0

The problem is in this line: int q = p + r / 2;

This should be int q = (p + r) / 2;

answered Mar 06 '18 at 14:25

Morad

2,761
21
29

What's wrong with my Merge sort java code?

2 Answers2