Before revision:  We also present a more involved O(n log n) time divide-and-conquer algorithm.
After revision:  We also present a more involved O(n \log n) time divide-and-conquer algorithm.