Postgres Pro
Downloads
Home   >   mailing lists

Re: Why do we still perform a check for pre-sorted input within qsort variants? - Mailing list pgsql-hackers

From Dann Corbit
Subject Re: Why do we still perform a check for pre-sorted input within qsort variants?
Date
Msg-id 87F42982BF2B434F831FCEF4C45FC33E5BD36A05@EXCHANGE.corporate.connx.com
Whole thread Raw
In response to Re: Why do we still perform a check for pre-sorted input within qsort variants?  (Dann Corbit <DCorbit@connx.com>)
List pgsql-hackers
Tree view 
"A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq"
By Eelis van der Weegen and James McKinna
Institute for Computing and Information Sciences
Radboud University Nijmegen
Heijendaalseweg 135, 6525 AJ Nijmegen, The Netherlands

Contains a formal proof, validated by machine logic, that quicksort is quadratic in the worst case and also a formal
proofof the average runtime efficiency.

pgsql-hackers by date:

Previous
From: Dann Corbit
Date:
Subject: Re: Why do we still perform a check for pre-sorted input within qsort variants?
Next
From: Greg Stark
Date:
Subject: Re: Why do we still perform a check for pre-sorted input within qsort variants?