Quicksort

[Helmut Prodinger <Helmut.Prodinger@tuwien.ac.at>]

Hi, Arnold Knopfmacher found in H. Wilf's book about Algorithms and
Complexity the
research problem about "splitters in permutations."

A permutation pi has a splitter if pi = sigma k tau,
k a number between 1 and n, and the elements in sigma smaller than k,
and the elements
in  tau [guess what: ] larger than k.

Question: what is the probability the a perm has a splitter
(asymptotically)?

Remember that Knuth tried to introduce "perm" for "permutation".

Was there any progress after Wilf's book?

    Best regards,

        Helmut Prodinger