From 22263709eda9f7d692a0f484fd759f757418dbd7 Mon Sep 17 00:00:00 2001 From: Rich Felker Date: Wed, 27 Apr 2011 13:27:04 -0400 Subject: replace heap sort with smoothsort implementation by Valentin Ochs Smoothsort is an adaptive variant of heapsort. This version was written by Valentin Ochs (apo) specifically for inclusion in musl. I worked with him to get it working in O(1) memory usage even with giant array element widths, and to optimize it heavily for size and speed. It's still roughly 4 times as large as the old heap sort implementation, but roughly 20 times faster given an almost-sorted array of 1M elements (20 being the base-2 log of 1M), i.e. it really does reduce O(n log n) to O(n) in the mostly-sorted case. It's still somewhat slower than glibc's Introsort for random input, but now considerably faster than glibc when the input is already sorted, or mostly sorted. --- COPYRIGHT | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'COPYRIGHT') diff --git a/COPYRIGHT b/COPYRIGHT index 92d8992e..b4b60d10 100644 --- a/COPYRIGHT +++ b/COPYRIGHT @@ -19,6 +19,10 @@ The implementation of DES for crypt (src/misc/crypt.c) is Copyright © 1994 David Burren. It is licensed under a BSD license compatible with the GNU LGPL. +The smoothsort implementation (src/stdlib/qsort.c) is Copyright © 2011 +Valentin Ochs and is licensed under an MIT-style license compatible +with the GNU LGPL. + The x86_64 port was written by Nicholas J. Kain. See individual files for their copyright status. -- cgit v1.2.1