Quicksort's asymptotic performance for array of [50,...,50,100,...100]
That depends very much on exactly what quicksort variant you use. Perhaps you should take a peek at Sedgewick "Quicksort with equal keys", SIAM J. Comp 6:2 (jun 1977), pp 240-267 (get it here) or Bentley, McIllroy "Engineering a sort function", Software: Practice &amp; Experience 23:11 (nov 1993), pp 1249-1265.