From 4d9a7fdc21730824f69d6e33e497dade864a170f Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Sun, 8 Nov 2015 11:46:10 -0800 Subject: quicksort: tail recurse on longer partition. * lib.c (quicksort): Sort the shorter partition with real recursion, then tail recurse with explicit goto to sort the longer partition. --- lib.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) diff --git a/lib.c b/lib.c index c060ed4b..e5c6b3fc 100644 --- a/lib.c +++ b/lib.c @@ -6393,7 +6393,7 @@ static cnum middle_pivot(val vec, val lessfun, val keyfun, cnum from, cnum to, static void quicksort(val vec, val lessfun, val keyfun, cnum from, cnum to) { - if (to - from >= 2) { + while (to - from >= 2) { val pkval; cnum i, j; cnum pivot = if3(to - from > 15, @@ -6408,8 +6408,13 @@ static void quicksort(val vec, val lessfun, val keyfun, cnum from, cnum to) swap(vec, num_fast(j), num_fast(to - 1)); - quicksort(vec, lessfun, keyfun, from, j); - quicksort(vec, lessfun, keyfun, j + 1, to); + if (j - from > to - j) { + quicksort(vec, lessfun, keyfun, j + 1, to); + to = j; + } else { + quicksort(vec, lessfun, keyfun, from, j); + from = j + 1; + } } } -- cgit v1.2.3