Wednesday, July 09, 2008

TwoFinger vs Quicksort

I also did some work on TwoFinger today. I have more than 100 tests with different sequences. None of the 3 varieties of Quicksort that I implemented (left, right and center pivot choice) is more efficient. In fact, I am having serious trouble finding a scenario in which TwoFinger is slower than Quicksort. While this apparent absence of evidence is not definite evidence of absence, the situation just makes me even more curious. There is still one thing I have not tried, and even then it's not clear TwoFinger should be slow (at least to me).

I also proved that TwoFinger is correct. It seems the worst case is not worse than n^2 / 4. The already sorted case, Quicksort's worst case, is extremely fast for TwoFinger. I have no idea of what is the average complexity. It looks like some sort of n log n, but I do not have proof for this yet.

More to come...

1 comment:

John Dougan said...

How does TwoFinger work?