  We revisit the classical problem of computing the \emph{contour tree} of a
scalar field $f:\mathbb{M} \to \mathbb{R}$, where $\mathbb{M}$ is a
triangulated simplicial mesh in $\mathbb{R}^d$. The contour tree is a
fundamental topological structure that tracks the evolution of level sets of
$f$ and has numerous applications in data analysis and visualization.
  All existing algorithms begin with a global sort of at least all critical
values of $f$, which can require (roughly) $\Omega(n\log n)$ time. Existing
lower bounds show that there are pathological instances where this sort is
required. We present the first algorithm whose time complexity depends on the
contour tree structure, and avoids the global sort for non-pathological inputs.
If $C$ denotes the set of critical points in $\mathbb{M}$, the running time is
roughly $O(\sum_{v \in C} \log \ell_v)$, where $\ell_v$ is the depth of $v$ in
the contour tree. This matches all existing upper bounds, but is a significant
improvement when the contour tree is short and fat. Specifically, our approach
ensures that any comparison made is between nodes in the same descending path
in the contour tree, allowing us to argue strong optimality properties of our
algorithm.
  Our algorithm requires several novel ideas: partitioning $\mathbb{M}$ in
well-behaved portions, a local growing procedure to iteratively build contour
trees, and the use of heavy path decompositions for the time complexity
analysis.
