We present a modification to the divide-and-conquer algorithm of Guibas & Stolfi [GS] for computing the Delaunay triangulation of n sites in the plane. The change reduces its &THgr;(n log n) expected running time to &Ogr;(n log n) for a large class of distributions which includes the uniform distribution in the unit square. The modified algorithm is significantly easier to implement than the optimal linear-expected-time algorithm of Bentley, Weide & Yao [BWY]. Unlike the incremental methods of Ohya, Iri & Murota [OIM] and Maus [M] it has optimal &Ogr;(n log log n) worst-case performance. The improvement extends to the composition of the Delaunay triangulation in the Lp metric for 1 p ≤ ∞. Experimental evidence presented demonstrates that in the Euclidean case the modified algorithm performs very well for n ≤ 216, the range of the experiments. We conjecture that its average running time is no more than twice optimal for n less than seven trillion.