0
$\begingroup$

I am studying this part for a merge sort implementation:

void mergeSort(int arr[], int l, int r) {
if (l < r)
{
    // Same as (l+r)/2, but avoids overflow for
    // large l and h
    int m = l+(r-l)/2;

    // Sort first and second halves
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);

    merge(arr, l, m, r);
}}

What is the meaning of:

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

in the code? Why can't I use (l+r)/2? (I didn't understand the comment)

$\endgroup$
1
$\begingroup$

Because of integer overflow, (l+r)/2 won't actually compute the midpoint like we want in some special cases. See https://stackoverflow.com/q/17358806/781723 and https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html for details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.