Exercise 1

I would expect you to find that the "efficient" implementation is much more efficient than the quadratic one for large input, and that the optimised library implementation is quite a bit faster than your own "efficient" implementation, but not wildly so.

As for testing, a good idea seems to be to test that the three implementations always give the same result (up to reordering of duplicates).

Exercise 2

Two possible answers:

If the input is likely to be partially sorted, then one can also consider using an adaptive sorting algorithm.

Exercise 3

Assume that the input consists of n elements, out of which n / c have the same key k. Then quicksort using this partitioning strategy (and no optimisations, such as switching to other sorting algorithms) requires Ω(n² / c²) steps.

Proof: Whenever the input is partitioned, all elements with key k end up in the same subset (S or S), except perhaps for one (the pivot). Quicksort does not terminate until every element has been selected as a pivot once, so we need to partition the input at least n / c times. Computing these partitions takes at least

  ∑ i = 1n / c i = Ω(n² / c²)

steps.