The sky's the limit! (Quickort on posets.)

["Marko Riedel" <mriedel@xxxxxxxxxxxxx>]

Hi folks,

I am so very grateful for your cooperation regarding the quickselect
disorder paper! I would like to return the favor by sharing an idea
that may well prove quite interesting, and, I believe, could perhaps
generate enough material for a paper, so read the following
closely. The diagrams will only work if your mail user agent uses a
fixed-width font.

Goal: exact analysis of quicksort on posets.

Observation: classic quicksort produces the poset consisting of a
single chain.

    *
    |
    *
    |
    *
    |     <- n items
    *
    |
    *
    |
    *
    |
    *

However, there's an infinite number of non-trivial posets that can be
produced with a modified quicksort. I show two examples:

I: fork.


    *
    |
    *
    |     <- n/2 items
    *
    |
    *
    |  
    *
   / \
  *   *            <- 2 x n/4 items
 /     \
*       *

This poset is produced by recursing as long as the interval being
sorted is partially or completely above the middle. The first interval
to contain all of the upper half of the data set triggers a subsequent
additional traditional quicksort on the first and the second quarter
of the data set.

II: ornament

    *
    |
    *
    |     <- n/3 items
    *
    |  
    *
   /|\
  * * *
 /  |  \
*   *   *              <- 3 x n/9 items
 \  |  /
  * * *
   \|/
    *
    |
    *
    |     <- n/3 items
    *
    |  
    *

This poset is obtained by recursing on all intervals containing some
part of the upper and lower third; the first recursive step where
these are completely sorted (the depth of the recursion where this
occurs varies) triggers an additional recursion: it splits the central
third into thirds and sorts them using traditional quicksort.

This idea could generate a lot of interesting material since all
connected posets are potential candidates for analysis. Keep in minde
that we definitely require exact asymptotics.

The algorithm is not very difficult since the internal recursive steps
of quicksort already use subintervals of the whole interval and this
is all that is needed for posets.

There is a fine variation on this, namely when you use subintervals
whose sizes are of different orders. E.g. in the above example all
subintervals are theta(n), but you could just as well analyse a fork
whose handle is theta(n) and whose tips are theta(sqrt(n)). Obviously
the handle contributes the dominant term in this case, but the exact
asymptotics are not as easy.

There's an additional challenge for deep thinkers here: recall how
there is a calculus for cover times of graphs. In principle these can
be computed for any graph by using submatrices of the stochastic
matrix obtained from the adjacency matrix of the graph. Can you
provide a calculus for the quicksort asymptotics for any connected
poset?

I'd be thrilled to get some feedback on this. Have fun!

Best regards,

-- 
+------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@neuearbeit.de |
| http://www.geocities.com/markoriedelde/index.html          |
+------------------------------------------------------------+