diff options
| author | Ori Bernstein <ori@eigenstate.org> | 2020-11-01 11:23:39 -0800 |
|---|---|---|
| committer | Ori Bernstein <ori@eigenstate.org> | 2020-11-01 11:23:39 -0800 |
| commit | b5086c1863fe10faf48ab675f503e562ec8dfcf0 (patch) | |
| tree | eda10b4fc690a80d2d742cfbe85c870cdbf11435 /sys/src/libc | |
| parent | 51b22d8548e61d3807b8b94e09d84f116ca0eb1c (diff) | |
libc: recurse on smaller half of array
Our qsort has an optimization to recurse on one
half of the array, and do a tail call on the other
half. Unfortunately, the condition deciding which
half of the array to recurse on was wrong, so we
were recursing on the larger half of the array and
iterating on the smaller half.
This meant that if we picked the partition poorly,
we were pessimizing our stack usage instead of
optimizing it.
This change reduces our stack usage from O(n)
to O(log(n)) for poorly chosen pivots.
Diffstat (limited to 'sys/src/libc')
| -rw-r--r-- | sys/src/libc/port/qsort.c | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/sys/src/libc/port/qsort.c b/sys/src/libc/port/qsort.c index 91c768c77..c38a49da7 100644 --- a/sys/src/libc/port/qsort.c +++ b/sys/src/libc/port/qsort.c @@ -100,7 +100,7 @@ qsorts(char *a, long n, Sort *p) j = (pj - a) / es; n = n-j-1; - if(j >= n) { + if(j < n) { qsorts(a, j, p); a += (j+1)*es; } else { |