Maximal derangements

When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement
of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like
to know whether there is a sensible general measure of derangements of n objects and
efficient algorithm to compute that measure and eventually also to determine the set representing maximal derangements.

I second Raphael's remark that when shuffling cards, you don't want the deck to be "unsorted", but rather random. However, when analyzing any specific shuffle, there can be measures of randomness that can be used to prove that a small number of shuffles isn't enough to make the deck random enough.

As a simple example, consider the "top card shuffle", in which you repeatedly take the top card and place it at an arbitrary location. If you don't repeat this enough times, then the top $k$ cards will retain their relative order (since you never put the top card somewhere among the top $k$ cards). So a reasonable measure of "sortedness" would be the maximal $k$ such that the top $k$ cards retain their relative order - for a shuffled deck, we expect this to be very small.

There is a similar measure for riffle shuffle, namely the number of ascents, two adjacent cards which retain their relative order. A random permutation has $n/2$ ascents, while an (under-)riffle-shuffled deck will have too many.

All this and more is described in David Aldous and Persi Diaconis, Shuffling cards and stopping times.

StackExchange Computer Science Q#6322, answer score: 5