Facts about sorting:

   Sorting algorithms that compare adjacent elements require quadratic time in the average case.

   Sorting algorithms that compare pairs of elements require time n log n in the worst case

    Quicksort requires time n log n in the average case


	Here we assume that for "average" input, each permutation is equally likely.  This is often an unrealistic assumption.