Search code examples
c++mergesortinteger-overflow

Avoiding Overflow using l+(r-l)/2

When I was learning Merge Sort implementation, I came across the code below:

// Same as (l+r)/2, but avoids overflow for 
// large l and h 
int m = l+(r-l)/2;

  1. How is (l+r)/2 same as l+(r-l)/2? The latter evaluates into r/2.

  2. How does (l+r)/2 cause overflow and how does l+(r-l)/2 fix the problem?

  3. What's h? (I think it's a typo which is meant to be r)

Solution

    1. Please check again - it expands to l + r/2 - l/2 which is l/2 + r/2. Note that we can't just use l/2 + r/2 as there will be integer truncation, so 3/2 + 5/2 = 1 + 2 = 3, but the desired value is 4.

    2. Assume that both l and r are positive values of type int.

    If we have:

    int l = INT_MAX - 2;
int r = INT_MAX;

    Then the l + r part is INT_MAX - 2 + INT_MAX, which is an integer overflow. INT_MAX - 2 + (INT_MAX - (INT_MAX - 2))/2 has no integer overflows as each sub-expression remains between INT_MIN and INT_MAX.

    1. Yes, that's a typo!