[TYPES] How fast is the fastest sorting program in type theories?

Yong Luo Y.Luo at kent.ac.uk
Fri Dec 1 07:45:57 EST 2006

Dear all,

I would like to know the complexity of Quicksort in type theories.

According to private conversation, the complexity of Quicksort in type
theories is: Cubic. But I am not sure whether it is a correct analysis.

I have implemented a type theory with pattern matching. The complexity of
Quicksort is O(n log n) in the best case (see the following link for

The complexity of Quicksort might be different for different
implementations. I would like to collect all the results and make a

Thank you,

Dr. Yong Luo
Computing Laboratory
University of Kent

More information about the Types-list mailing list