Summary: We present a truly practical and provably optimal \(O(n\log h)\) time output-sensitive algorithm for the planar convex hull problem. The basic algorithm is similar to the algorithm presented by \textit{T. M. Chan}, \textit{J. Snoeyink}, and \textit{C. K. Yap} [Clarkson, K. (ed.), Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 22-24, 1995. Philadelphia, PA: SIAM, 282-291 (1995; Zbl 0848.68106)] where the median-finding step is replaced by an approximate median. We analyze two such schemes and show that for both methods, the algorithm runs in expected \(O(n\log h)\) time. We further show that the probability of deviation from expected running time approaches 0 rapidly with increasing values of \(n\) and \(h\) for any input. Our experiments suggest that this algorithm is a practical alternative to the worst-case \(O(n\log n)\) algorithms such as Graham's and is especially faster for small output-sizes. Our approach bears some resemblance to a recent algorithm of \textit{R. Wenger} [Algorithmica (to appear)], but our analysis is substantially different.