  Divide-and-conquer is a central paradigm for the design of algorithms,
through which some fundamental computational problems, such as sorting arrays
and computing convex hulls, are solved in optimal time within
$\Theta(n\log{n})$ in the worst case over instances of size $n$. A finer
analysis of those problems yields complexities within $O(n(1 + \mathcal{H}(n_1,
\dots, n_k))) \subseteq O(n(1{+}\log{k})) \subseteq O(n\log{n})$ in the worst
case over all instances of size $n$ composed of $k$ "easy" fragments of
respective sizes $n_1, \dots, n_k$ summing to $n$, where the entropy function
$\mathcal{H}(n_1, \dots, n_k) = \sum_{i=1}^k{\frac{n_i}{n}}\log{\frac{n}{n_i}}$
measures the "difficulty" of the instance. We consider whether such refined
analysis can be applied to other algorithms based on divide-and-conquer, such
as polynomial multiplication, input-order adaptive computation of convex hulls
in 2D and 3D, and computation of Delaunay triangulations.
