Thursday, July 10, 2008

TwoFinger update of the day

I did some more work, and I found a way to create a worst case scenario for TwoFinger. The performance is indeed n^2. With some trepidation (I confess) I measured the worst case for TwoFinger with Quicksort, and the worst case for Quicksort with TwoFinger. The result? TwoFinger is significantly more efficient in both cases.

I also tried a set of about 160k random doubles. TwoFinger was more efficient than Quicksort in terms of performed probes (accesses to the collection being sorted), swaps, and object comparisons.

Perhaps there is a remote chance that this is worth the effort.

Maybe. I wonder what the beta testers will say about it.

No comments: