Insertion Sort is O(n log n)

Michael A. Bender, Martin Farach-Colton, Miguel Mosteiro

Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accele…