  Bucket Sort is known to run in expected linear time when the input keys are
distributed independently and uniformly at random in the interval $[0,1)$. The
analysis holds even when a quadratic time algorithm is used to sort the keys in
each bucket. We show how to obtain linear time guarantees on the running time
of Bucket Sort that hold with very high probability. Specifically, we
investigate the asymptotic behavior of the exponent in the upper tail
probability of the running time of Bucket Sort. We consider large additive
deviations from the expectation, of the form $cn$ for large enough (constant)
$c$, where $n$ is the number of keys that are sorted.
  Our analysis shows a profound difference between variants of Bucket Sort that
use a quadratic time algorithm within each bucket and variants that use a
$\Theta(b\log b)$ time algorithm for sorting $b$ keys in a bucket. When a
quadratic time algorithm is used to sort the keys in a bucket, the probability
that Bucket Sort takes $cn$ more time than expected is exponential in
$\Theta(\sqrt{n}\log n)$. When a $\Theta(b\log b)$ algorithm is used to sort
the keys in a bucket, the exponent becomes $\Theta(n)$. We prove this latter
theorem by showing an upper bound on the tail of a random variable defined on
tries, a result which we believe is of independent interest. This result also
enables us to analyze the upper tail probability of a well-studied trie
parameter, the external path length, and show that the probability that it
deviates from its expected value by an additive factor of $cn$ is exponential
in $\Theta(n)$.
