Fast-insertion-sort: A new family of efficient variants of the insertion-sort algorithm

In this paper we present Fast-Insertion-Sort, a sequence of efficient external variants of the well known Insertion-Sort algorithm which achieve by nesting an O(n1+ε) worst-case time complexity, where ε = h1 , for h ∈ N. Our new solutions can be seen as the generalization of Insertion-Sort to multiple elements block insertion and, likewise the original algorithm, they are stable, adaptive and very simple to translate into programming code. Moreover they can be easily modified to obtain in-place variations at the cost of a constant factor. Moreover, by further generalizing our approach we obtain a representative recursive algorithm achieving O(nlog n) worst case time complexity. From our experimental results it turns out that our new variants of the Insertion-Sort algorithm are very competitive with the most effective sorting algorithms known in literature, outperforming fast implementations of the Hoare's Quick-Sort algorithm in many practical cases, and showing an O(nlog n) behaviour in practice.