On Sat, May 20, 2017 at 10:20:42AM +0200, Otto Moerbeek wrote:
> On Fri, May 19, 2017 at 09:04:30AM -0600, Todd C. Miller wrote:
>
> > On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote:
> >
> > > I believe the best approach is to switch qsort.c to "introsort".
> > > The changes are mini
On Fri, May 19, 2017 at 09:04:30AM -0600, Todd C. Miller wrote:
> On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote:
>
> > I believe the best approach is to switch qsort.c to "introsort".
> > The changes are minimal and the elimination of the O(n^2) worst
> > case is compelling.
>
> I'v
On Thu, 18 May 2017 09:58:14 -0600, "Todd C. Miller" wrote:
> I believe the best approach is to switch qsort.c to "introsort".
> The changes are minimal and the elimination of the O(n^2) worst
> case is compelling.
I've added input arrays to the qsort regress test that exhibit
quadratic behavior
On Wed, 17 May 2017 19:15:45 +0200, Ingo Schwarze wrote:
> For the record, this commit changes worst-case stack space requirements
> from O(n) to O(log n). The following are unchanged:
>
> - average stack space: O(log n)
> - average run time: O(n log n)
> - worst case run time: O(n^2)
>
