What's the difference in merge sort? mid = left + (right - left) / 2 and mid = (left + right) / 2

Question

I came across under code.

private static <T extends Comparable<T>> void doSort(T[] arr, int left, int right) {
    if (left < right) {
      int mid = left + (right - left) / 2;
      doSort(arr, left, mid);
      doSort(arr, mid + 1, right);
      merge(arr, left, mid, right);
    }
}

I think there is no difference between left + (right - left) / 2 and mid = (left + right) / 2

Can anyone explain the difference?

thank you!

score 3 · Accepted Answer · answered Feb 03 '21 at 00:43

3

Integers can overflow if the array gets big enough.

(left + right) / 2 is problematic as left + right overflows. left + (right - left) / 2 prevents that.

answered Feb 03 '21 at 00:43

Philipp Claßen

41,306
31
146
239

2

for somebody who may think *the division avoids the overflow* , remember `left+right` is evaluated first – aran Feb 03 '21 at 00:47

What's the difference in merge sort? mid = left + (right - left) / 2 and mid = (left + right) / 2

1 Answers1