Bug in quicksort example (K&R C book)?

Question

This quicksort is supposed to sort "v[left]...v[right] into increasing order"; copied (without comments) from The C Programming Language by K&R (Second Edition):

void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)
        return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left+1; i <= right; i++)
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

I think there's a bug at

(left + right) / 2

Suppose left = INT_MAX - 1 and right = INT_MAX. Wouldn't this result in undefined behavior due to integer overflow?

Bergius

It was probably programmed with the assumption that an array wouldn't be that large at runtime. :) – Cyano

That's a very good assumption since you wouldn't have space in memory for your quicksort program – Tombstone

See also: googleresearch.blogspot.com/2006/06/… – Sondra

@Bergius can you please answer this question? https://mcmap.net/q/540440/-quick-sort-programmed-in-c – Gavotte

Answer 1

Yes, you're right. You can use left - (left - right) / 2 to avoid overflows.

Suzysuzzy

@Jerry / Paul: Which, since (right - left) == - (left - right), is the same as this answer's formulation. – Hallelujah

@caf: Ah, I hadn't thought of it that way, but you're right. I rescind my original comment, and apologize for being obtuse. – Riti

Answer 2

You aren't imagining an array with INT_MAX number of elements, are you?

Palaeozoic

That's just under 8 gigabytes of address space, assuming 32-bit integers. More than doable on modern hardware. :) – Cyano

We would probably have to excuse K&R for not considering memory growing from kB to GB. And "640k should be enough for everyone"? – Unsocial

@Bo there are platforms with 16-bit ints, you know, and I'm pretty sure some of them have more than 64Kb of memory. int != intptr_t. – Stockjobber

Answer 3

Yes, you're right, although it's possibly just written that way for simplicity -- it's an example after all, not production code.

Holliman

Answer 4

K&R was always a bit sloppy with their use of unsigned vs signed arguments. Side effect of working with a PDP that had only 16 kilobytes of memory I suppose. That's been fixed a while ago. The current definition of qsort is

void qsort(
   void *base,
   size_t num,
   size_t width,
   int (__cdecl *compare )(const void *, const void *) 
);

Note the use of size_t instead of int. And of course void* base since you don't know what kind of type you are sorting.

Unconventional

The __cdecl wart isn't a part of the standard definition. – Hallelujah

I'm sure that's true, they probably had only one calling convention back then. And a lot less keywords that started with two underscores. Leave it up to the vendors to make it complicated. Necessarily so, the standard kinda sux. – Unconventional