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.

1 files changed, 2 insertions, 1 deletions

diff --git a/src/lib/libc/stdlib/heapsort.c b/src/lib/libc/stdlib/heapsort.c
index 878567729e..f1db2205b0 100644
--- a/src/lib/libc/stdlib/heapsort.c
+++ b/src/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);