Why "int mid = (left - right)/2 + right" will cause stack overflow?

Question

I wrote the code of merge sort today, and I meet a StackOverFlow error when I run int mid = (left - right)/2 + right;. But when I use int mid = left + (right - left) / 2; everything is fine. I'm very confused because the mathematical meaning of the two of them is the same(if it's not, why?).

I have seen this question but I'm not sure it answers this problem. why left+(right-left)/2 will not overflow?

Here's my code，I am sorry that I did not upload the code before.

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] array = {3,5,1,2,4,8};
        int[] result = mergeSort(array);
        System.out.println(Arrays.toString(result));
    }

    public static int[] mergeSort(int[] array) {
        if (array == null || array.length <= 1) {
            return array;
        }
        int[] helper = new int[array.length];
        sort(array, helper, 0, array.length - 1);
        return array;
    }

    public static void sort(int[] array, int[] helper, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left - right)/2 + right;
        //int mid = left + (right - left) / 2;
        sort(array, helper, left, mid);
        sort(array, helper, mid + 1, right);

        combine(array, helper, left, mid, right);
    }

    public static void combine(int[] array, int[] helper, int left, int mid, int right) {
        for (int i = left; i <= right; i++) {
            helper[i] = array[i];
        }

        int leftIndex = left;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right) {
            if (helper[leftIndex] <= helper[rightIndex]) {
                array[left] = helper[leftIndex];
                left++;
                leftIndex++;
            } else {
                array[left] = helper[rightIndex];
                left++;
                rightIndex++;
            }
        }

        while (leftIndex <= mid) {
            array[left] = helper[leftIndex];
            left++;
            leftIndex++;
        }
    }
}

`I'm very confused because the mathematical meaning of the two of them is the same.` no it's not. — tkausl, Jan 15 '19 at 22:27
Please [edit] your question and show us the complete code of your method. Not just one line ([edit] your question, do not put code in comments) — , Jan 15 '19 at 22:27
Just to be clear, what you are talking about is *integer overflow*, not a *stack overflow*. If you are receiving a `StackOverflowError`, then your problem is somewhere else. — 0x5453, Jan 15 '19 at 22:29
That line, on its own, will not cause a `StackOverflowError`. — Joe C, Jan 15 '19 at 22:30
Why are you not satisfied with the answers to the question you linked to? — PM 77-1, Jan 15 '19 at 22:32
No, it is a `StackOverflowError`. It's because integer division on negative numbers rounds towards zero. So when you get to `right = 1 + left`, then `mid` comes out the same as `right`. Depending on how the REST of your code handles this, you might recurse endlessly. Now - if you show ALL of your code (not just one line), somebody might be able to suggest a fix. — Dawood ibn Kareem, Jan 15 '19 at 22:37
@PM77-1 presumably because the linked question is about Integer overflows, but OP is getting a Stack overflow, which is entirely different. — Dawood ibn Kareem, Jan 15 '19 at 22:39
@tkausl They _are_ equal mathematically. Both shorten to `int mid = (left + right) / 2`. — marstran, Jan 15 '19 at 22:41
@DawoodibnKareem Thanks for your response, I just uploaded the entire code. — Meilan, Jan 15 '19 at 22:45
@marstran, No they are NOT mathematically equal. If `left = 0` and `right = 1`, then `(left - right)/2 + right` is `1` and `left + (right - left) / 2` is `0`. — Dawood ibn Kareem, Jan 15 '19 at 22:45
(Note, to avoid the integer overflow for positive signed integers you should write it as `int mid = (left+right) >>> 1;`. Josh Bloch has written about this in relation to the collections library (binary search I guess, and/or sorts). Integer overflows are often the underlying cause of buffer overflows (typically caught in Java) including stack buffer overflows (not Java), but can manifest in other ways. Dealing with integer overflows with "big integers" is not fun.) — Tom Hawtin - tackline, Jan 15 '19 at 22:49
And `(left + right) / 2` is different again, because of the integer overflow problem, as explained in the linked question. — Dawood ibn Kareem, Jan 15 '19 at 22:49
@DawoodibnKareem Calculate that again. `(left - right) / 2 + right` = `(0 - 1) / 2 + 1` = `0.5 + 1` = `0.5`. And `left + (right - left) / 2` = `0 + (1 - 0) / 2` = `1 / 2` = `0.5`. So _mathematically_, they are equal. With integer arithmetic however... — marstran, Jan 15 '19 at 22:51
Yeah, OP is doing integer arithmetic. `1 / 2` is NOT `0.5` in Java. — Dawood ibn Kareem, Jan 15 '19 at 22:52
@DawoodibnKareem That's why I specified _mathematically_.... — marstran, Jan 15 '19 at 22:53
@marstran Thank you, I guess I should read some materials about integer overflow. — Meilan, Jan 15 '19 at 22:55
The integer overflow only becomes relevant when `left` or `right` get over a billion. If you've got an array with a billion elements, you're likely to have other problems. So the advice about NOT writing `(left + right)/2`, while technically correct, is not particularly useful in the "real world". — Dawood ibn Kareem, Jan 15 '19 at 23:03

score 2 · Accepted Answer · answered Jan 15 '19 at 22:55

As you run this, sooner or later, it's likely that left will be one less than right - for example, maybe left = 3 and right = 4.

In that case, (left - right) / 2 and (right - left) / 2 both evaluate to 0, since integer division rounds towards zero. So, if you have

int mid = (left - right)/2 + right;
sort(array, helper, left, mid);

within your call to sort(array, helper, left, right), then you're repeating a call with the exact same values. This causes infinite recursion - a StackOverflowError.

But when you have

int mid = left + (right - left)/2;
sort(array, helper, left, mid);

then you're repeating a call with different values, so the recursion has a chance to end.

score 0 · Answer 2 · answered Dec 23 '21 at 17:16

Initially, you have left < right. And, of course, right - left > 0, and furthermore left + (right - left) = right (follows from basic algebra).

And consequently left + (right - left) / 2 <= right. So no overflow can happen since every step of the operation is bounded by the value of right.

Why "int mid = (left - right)/2 + right" will cause stack overflow?

2 Answers2