diff options
| author |   millert <millert@openbsd.org> | 2017-05-20 12:48:56 +0000 |
|---|---|---|
| committer | millert <millert@openbsd.org> | 2017-05-20 12:48:56 +0000 |
| commit | 4520aa4f05703eeee22781f0c24f3cdcd1421431 (patch) | |
| tree | 2efb5b01fef1e84d7ca349b7bfee07d144584a3d /lib/libc/stdlib/heapsort.c | |
| parent | Mention that not all varaints support baud rates up to 2 Mbps. (diff) | |
| download | wireguard-openbsd-4520aa4f05703eeee22781f0c24f3cdcd1421431.tar.xz wireguard-openbsd-4520aa4f05703eeee22781f0c24f3cdcd1421431.zip | |
Use David Musser's introsort algorithm to fall back to heapsort(3)
when the recursion depth reaches 2*lg(n + 1). This avoids quicksort's
quadratic behavior for pathological input without appreciably
changing the average run time.
Diffstat (limited to 'lib/libc/stdlib/heapsort.c')
| -rw-r--r-- | lib/libc/stdlib/heapsort.c | 3 |
1 files changed, 2 insertions, 1 deletions
diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c index 878567729e9..f1db2205b0d 100644 --- a/lib/libc/stdlib/heapsort.c +++ b/lib/libc/stdlib/heapsort.c @@ -1,4 +1,4 @@ -/* $OpenBSD: heapsort.c,v 1.10 2016/10/22 19:19:34 tb Exp $ */ +/* $OpenBSD: heapsort.c,v 1.11 2017/05/20 12:48:56 millert Exp $ */ /*- * Copyright (c) 1991, 1993 * The Regents of the University of California. All rights reserved. @@ -172,3 +172,4 @@ heapsort(void *vbase, size_t nmemb, size_t size, free(k); return (0); } +DEF_WEAK(heapsort); |