From ace460cb1c24d1dc9a5b0156cefbc6bce235b73d Mon Sep 17 00:00:00 2001 From: "W. Trevor King" Date: Mon, 25 Oct 2010 11:55:31 -0400 Subject: [PATCH] Protect quicksort pivot index from overflow. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Mentioned on http://en.wikipedia.org/wiki/Quicksort Note the left + (right-left)/2 expression. (left + right)/2 would seem to be adequate, but in the presence of overflow, can give the wrong answer; for example, in signed 16-bit arithmetic, 32000 + 32000 is not 64000 but -1536, and dividing that number by two will give you a new pivotIndex of -768 — obviously wrong. --- src/sorting/quicksort.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/sorting/quicksort.c b/src/sorting/quicksort.c index 0d82e07..d763335 100644 --- a/src/sorting/quicksort.c +++ b/src/sorting/quicksort.c @@ -16,7 +16,7 @@ void swap(double *x, double *y) int choose_pivot(int i, int j) { - return ((i + j) / 2); + return i + (j - i) / 2; } /* sort the list from list[m] to list[n] */ -- 2.26.2