Saturday, July 12, 2008

TwoFinger (apparently) revealed for what it is

I started suspecting that TwoFinger was a particular case of Quicksort. And apparently, it is equivalent to Quicksort in this configuration:

  • Center pivot
  • Two finger partition sorting (efficient when the list is already sorted, every element of the partition is moved exactly once except maybe the pivot, harder to get n^2 cases)
  • Using R. Sedgewick's idea of recursing on the smallest sublist and using tail recursion for the larger one (efficient use of the stack)
No wonder it was scoring so much better than a less sophisticated Quicksort...

Now, the final details need to be worked out. In particular, how does it compare to VW's hybrid sort as implemented in SortedCollection?...

No comments: