Error in quicksort example (K & RC book)?

Question

This quicksort should sort "v [left] ... v [right] in ascending order"; (no comment) from the C & K programming language (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 is a mistake in

 (left + right) / 2 

Suppose left = INT_MAX - 1 and right = INT_MAX. Could this lead to undefined behavior due to integer overflow?

Answer 1

Yes you are right. You can use left - (left - right) / 2 to avoid overflow.

Answer 2

You cannot imagine an array with INT_MAX number of elements, right?

Answer 3

Yes, you are right, although perhaps it’s just written for simplicity - this is an example, not production code.

Answer 4

K & R has always been a bit sloppy with unsigned vs signed arguments. A side effect of working with PDP, which had only 16 kilobytes of memory, I suppose. This was fixed some time ago. Current qsort definition

 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 type of sorting you are sorting.