In this paper we present Fast-Insertion-Sort, a sequence of efcient external variants of the well known Insertion-Sort algorithm which achieve by nesting an O(n1+") worst-case time complexity, where " = h1 , for h 2 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 modi ed 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(n log 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 e ective sorting algorithms known in literature, outperforming fast implementations of the Hoare's Quick-Sort algorithm in many practical cases, and showing an O(n log n) behaviour in practice.
Sorting is one of the most fundamental and extensively studied problems in computer science, mainly due to its direct applications in almost all areas of computing and probably it still remains one of the most frequent tasks needed in almost all computer programs.
Formally sorting consists in nding a permutation of the elements of an input array such that they are organized in an ascending (or descending) order. In the comparison based model, it is well-known that the lower bound for sorting n distinct elements is (n log n), both in the worst case and in the average case.1
A huge number of e cient sorting algorithms have been proposed over the years with di erent features.2 There are several factors indeed a ecting the selec
Insert(A; i) 1. j i 1 2. v A[i] 3. while (j 0 and A[j] > v) do 4. A[j + 1] A[j] 5. j j 1 6. A[j + 1] v
InsertionSort
1. for i 1 to n 1 do
2. Insert(A; i)
tion of suitable sorting algorithm for an application [
The space complexity of an algorithm concerns the total amount of working
space (in addition to the array to be sorted) required in the worst case. An
inplace algorithm requires only constant additional space, otherwise it is said to
be an external algorithm. However, in literature, many recursive algorithms are
said to work in-place (using ambiguous terminology) even if they do not, since
they require a stack of logarithmic height. In this case we say that the algorithm
is internal [
The focus of many sorting algorithms lies instead on practical methods whose running time outperforms standard techniques even when comparisons are cheap. In this case expected (rather than worst case) performances is the main concern. Among this class of algorithms, despite its higher number of comparisons than for other methods, Quick-Sort and most of its variants are generally considered the fastest general purpose sorting methods.
The Insertion-Sort algorithm, particularly relevant for this paper, is also
considered one of the best and most exible sorting methods despite its quadratic
worst case time complexity, mostly due to its stability, good performances,
simplicity, in-place and online nature. It is a simple iterative sorting procedure that
incrementally builds the nal sorted array. Its pseudocode is depicted in Fig. 1.
The i-th iteration of the algorithm takes at most O(i) time, for a total O(n2)
time complexity in both worst and average case.
Algorithm twc
Insertion-Sort O(n2)
Rotated-IS [
O(w)? O(n2) 1979
O(n) O(n log n) 1980 O(n log n) O(n) O(n log n) O(n) 2006 O(n log n) O(1) O(n2) O(n log n) 2008 O(n2) O(1) O(n2) O(n) 2010 O(n2) O(n) O(n2) O(n) 2013 O(n log n) O(1) O(n2) O(n) 2014 O(n2) O(1) O(n2) O(n) 2015 O(n2) O(1) O(n1:5) O(n2) 2017 O(n2) O(1) O(n2) O(n) 2018 O(n log n) O(1) O(n2) O(n) 2018 O(n log n) O(1)[ O(n log n)x O(n) 2019 O(n log n) O(1)[ O(n log n)x O(n) 2019
O(n log n) O(1)[ O(n log n)x O(n) 2019
The Insertion-Sort algorithm is also adaptive, achieving O( n) worst case time
complexity when each element in the input array is no more than places away
from its sorted position. Moreover it has an enviable linear best case time (which
occurs when the input array is already sorted) and can be immediately translated
into programming code (see Bentley [
Much more interesting, Insertion-Sort is one of the fastest algorithms for
sorting very small arrays, even faster than Quicksort [
Due to such many advantages the Insertion-Sort algorithm has inspired much work and is the progenitor of several algorithmic variants which aim at reducing comparisons and element moves very e ciently. Table 1 presents a list of most of e ective variants of Insertion-Sort portrayed in terms of several features.
For the sake of completeness we also report the some related algorithms
obtained as the combination of Merge-Sort and Insertion-Sort [
In this paper we present a new family of e cient external algorithms inspired by Insertion-Sort, where each element of the family, named Fast-Insertion-Sort(h) for h 2 N, achieves an O(n1+ h1 ) worst-case time complexity by nesting previous algorithms of the same family. Although Fast-Insertion-Sort(h) requires O(n1 h1 ) additional space we show how to translate it into an in-place solution at the cost of a constant factor. In addition we also devise a purely recursive generalized version of our Fast-Insertion-Sort(h) algorithms, which achieves an O(n log n) worst case time complexity. Like Insertion-Sort our solutions are stable, adaptive and very simple to translate into programming code.
Surprisingly, it turns out from our experimental results that our variants of the Insertion-Sort algorithm are very e ective in practical cases showing an O(n log n) behaviour in practice. Their performances are comparable to that of the most e ective sorting algorithms known in literature, overcoming fast implementations of the Hoare's Quick-Sort algorithm in many practical cases.
Throughout the paper we will use the following terminology. Given an array A[0::n 1], of size n, we denote by A[i] the (i + 1)-st element of A, for 0 i < n, and with A[i::j] the portion of the array contained between the (i + 1)-st and the (j + 1)-st characters of A, for 0 i j < m. We indicate by (A + i) the array beginning at (i + 1)-st position of A, so that (A + i)[0::j] = A[i::j]. 2
The Fast-Insertion-Sort Algorithms In this section we present Fast-Insertion-Sort, a new family of e cient sorting algorithms obtained as natural generalizations to multiple elements insertion of the standard Insertion-Sort algorithm. The underlying idea is to extend, at each iteration, the left portion of the array by means of the insertion of a sorted block of k elements, with k 2. Despite its simplicity, this approach surprisingly leads, under suitable conditions, to a family of very e cient algorithms, both in theory and in practice, whose behaviour moves close to a linear trend for increasing values of the input size.
The new family is a sequence of nested algorithms, Fast-Insertion-Sort(h), for h 2 N, where the h-th algorithm can be applied when n > 2h. The pseudocode of the Fast-Insertion-Sort(h) algorithm and its auxiliary procedure Insert-Block are depicted in Fig. 2.
Each algorithm in the sequence solves the problem by nesting function calls to previous algorithms in the same sequence and is associated with an integer parameter h > 0 which substantially represents the depth of such a nesting. For this reason in the execution of the Fast-Insertion-Sort(h) algorithm it is assumed that the size of the input array is at least 2h.
The following de nition of input size degree is particularly useful for the characterization of our algorithm.
De nition 1 (Input size degree). Given an input array of size n and a constant parameter c 2, we say that its input size degree (or simply its degree) is h, with reference to c, if ch 1 < n ch. We refer to the constant value c as the partitioning factor. When c is clear from the context we simply say that the input size degree is h. We can easily compute the degree of the input n by h = dlogc(n)e. Insert-Block(A; i; k; T ) Fast-Insertion-Sort(h)(A; n) 1. for j 0 to k 1 do 1. if n 2h 1 then h dlog2(n)e 2. Swap(T [j]; A[i + j]) 2. k n(h 1)=h 3. ` k 1 3. T 4. j i 1 4. for i 5. while ` 0 do 5. 6. while j 0 and A[j] > T [`] 6. 7. Swap(A[j + ` + 1]; A[j]) 7. 8. j j 1 9. Swap(A[j + ` + 1]; T [h]) 10. ` ` 1 array[k]
0 to n (step k) do b min(k; n i) Fast-Insertion-Sort(h 1)(A + i; b) Insert-Block(A; i; b; T )
Note 1 (Block partitioning). If the the input array has degree h then the algorithm performs a partitioning of the array in at most c blocks of size k = n1 h1 . In the worst case, indeed, n = ch and the number of blocks is given by n k =
n n1 h1
l 1 m = n h = l ch h1 m = c In addition observe that each block of size k represents an array of degree h Indeed, if ch 1 < n ch then k = n1 h1 is bounded by 1. ch 2 < ch 2+ h1 < ch 1 1 h1 < k ch 1 h1 = ch 1 Observe that if n < ch then the last block has size greater than 0 and less than k, thus we have no guarantees that such size has degree equal to h 1.
The algorithm is based on an iterative cycle on the variable i. At the beginning of each iteration, the left portion of the array, A[0::i 1], is assumed to be already sorted. Then the algorithm sorts the elements in the block A[i::i + k 1], of size k, by a nested call to Fast-Insertion-Sort(h 1), and tidily insert all the elements of the block in the sorted portion of the array by means of procedure Insert-Block. The overall number of iterations is then equal to dn=ke, where the size of the last block my be less than k and speci cally it has size n k(dn=ke 1).
A call to procedure Insert-Block(A; i; k; T ) has the e ect to insert the block A[i::i + k 1], of size k, into the left side of the array A[0::i 1], using the array T as a working area. It is assumed that both A[0::i 1] and A[i::i + k 1] have both been sorted. During the insertion process elements of the left portion will be moved over the elements of the right block in order to make room for the insertions. The additional array T , of size k, is used to temporarily store the elements of the right block so that they are not overwritten.
Note 2. Since procedure Insert-Block uses external memory for temporarily storing the elements of the block A[i::i + k 1], all swap operations (Swap(a; b)) inside the procedure (lines 2, 7 and 9), may be replaced by element moves (a b), cutting down the number of assignements of a factor up to 3.
The insertion process iterates over the elements of the right block (now temporarily moved on T ) proceeding from right to left (while cycle of line 5). For each element T [`], with 0 ` < k, the algorithm iterates over the elements A[j] of the left block, proceeding from right to left, in order to nd the correct position where T [`] must be placed (while cycle of line 6). If the element A[j] is greater than T [`] then it is moved of ` position to the right (line 7). Once the rst element A[j], such that A[j] T [`], is found (or j < 0), T [`] is moved at position A[j + ` + 1] and ` is decreased (lines 9-10).
Note 3. For simplicity procedure Insert-Block shown in Fig. 2 uses a linear
search for locating the correct position where an element must be placed. It
takes at most O(i) comparisons, if i is the size of the sorted portion of the array.
However it is more favourable to use a binary search [
It is easy to prove that all Fast-Insertion-Sort(h) algorithms maintain all the features of the standard Insertion-Sort algorithm and speci cally they guarantee a stable sorting and are very simple to implement. However a drawback of this family of algorithms is that they use additional external memory of size O(k). In the Section 2.1 we show how to obtain in-place variants of such algorithms.
Observe that Fast-Insertion-Sort(1) corresponds to the standard Insertion-Sort algorithm where k = n0 = 1 and each block consists in a single element.
The algorithm Fast-Insertion-Sort(2) devises a special mention since it can be
easily translated into a purely iterative in-place online adaptive sorting
algorithm. Due to its distinctiveness we give it a special name: Block-Insertion-Sort.
It can be proved that if we set k = pn then the worst-case time complexity of
Block-Insertion-Sort is O(n1:5). Although there are few variants [
The sequence of algorithms Fast-Insertion-Sort(h), for h 2 N, converge to a purely recursive algorithm which could be seen as the representative of the family and which, for this reason, we name simply Fast-Insertion-Sort. The pseudocode of the Fast-Insertion-Sort algorithm is depicted in Fig. 4. It maintains the main structure of the Fast-Insertion-Sort(h) algorithms but dynamically computes the value of the input size degree h. Speci cally, given a partitioning parameter c 2, the algorithm computes the input size degree as h = dlogc(n)e. The choice of the partitioning parameter c could be critical for the practical performances of the algorithm3. Note that, for c = 2, Fast-Insertion-Sort exactly behaves like 3 As discussed in Section 3 the best choice for the partitioning parameter, leading to the best performances in practical cases, is to set c = 5.
Fig. 3. Three schemas for the insertion of (A) a sorted block of size k into A[0::i 1].
Two blocks are involved: the working area w which represents the block to be inserted, and a storage area s, which is used (B) to temporarily store elements of the working area. In schema (A) an external storage area T is used. In schema (B) the contiguous block A[i + k::i + 2k 1] is used as (C) storage area. In schema (C) we insert the block A[i + k::i + 2k 1] and use the block A[i::i + k 1] as storage area.
Merge-Sort, since the process of inserting a sorting block into another one can be viewed as a merging procedure. It can be proved that the Fast-Insertion-Sort algorithm has a O(n log n) worst case time complexity. Moreover such algorithm shows also very good performances in practical cases, as discussed in Section 3. 2.1
In-Place Sorting In this section we brie y describe how to allow Fast-Insertion-Sort algorithms to use an internal storage area to temporarily save the elements of the working area representing the block which should be inserted during the current iteration, making it an in-place sorting algorithm4.
In order to make sure that the contents of the storage area is not lost, it is su cient to guarantee that whenever an element should be moved from the working area, it is swapped with the element occupying that respective position in the storage area. Procedure Insert-Block, shown in Fig. 2, makes this guarantees.
In this context it should be possible to use the contiguous block A[i + k::i + 2k 1], of size k, as storage area, as depicted in Schema B of Fig. 3. This could be obtained by replacing the procedure call Insert-Block(A; i; k; T ) (line 6) with Insert-Block(A; i; k; A + k). The main advantage of this approach is that the part of the array that is not currently being sorted can be used as temporary storage area. This yields a fast variant for the Fast-Insertion-Sort(h) algorithm which works in-place requiring only constant extra space.
However, since the insertion of a block of size k requires a contiguous block
of k elements, at the last iteration, when i > n 2k, there is not enough space to
allow the algorithm to work in-place. Although many solutions may be adopted
to address such case, we will prove it is enough to insert the elements of the last
4 This idea is not original since it has been successfully used in literature. The rst
sorting algorithm which introduced such a technique was the Quick-Heap-Sort
algorithm by Cantone and Cincotti [
Fast-Insertion-Sort(A; n) 1. if n 2 then 2. return Insertion-Sort(A; n) 3. h dlogc(n)e 4. k n(h 1)=h 5. T 6. for i 7. 8. 9.
array[k]
0 to n (step k) do b min(k; n i) Fast-Insertion-Sort(A + i; b)
Insert-Block(A; i; b; T ) block, whose size is at most 2k 1, by individual insertions, as done by standard Insertion-Sort.
Thus at the beginning of each iteration the two blocks A[i::i + k 1] and A[i + k::i + 2k 1] will be swapped. Subsequently, as in the previous case, the algorithm sorts the block A[i::i + k 1], of size k, and insert it in the sorted portion of the array, using the block A[i + k::i + 2k 1], as storage area.
However, since all elements of the array must be inserted, sooner or later, it is possible to avoid the k swap operation necessary to move the elements in the storage area (lines 1-2 of procedure Insert-Block) by interchanging the two blocks involved in the insertion process. Speci cally we can directly insert the block A[i + k::i + 2k 1] using the block placed in the middle, i.e. A[i::i + k 1], as storage area, as depicted in Schema C of Fig. 3.
It is easy to prove that the resulting in-place variants of the Fast-InsertionSort(h) algorithms maintain most of the features listed above: they work online and are very simple to implement. Unfortunately, due to the swap operations performed on the storage area, they don't guarantee a stable sorting and their performance are a bit worse than the corresponding external variants. 3
In this section we present and comment the experimental results relative to a
comparison of our newly presented algorithms against some of the most e
ective sorting algorithms known in literature. Speci cally we tested the following
algorithms:
{ Merge-Sort (MS), the external algorithm with a (n log n) time and O(n)
space complexity. Here we implemented a version using only an array of size
dn=2e as storage space.
{ Heap-Sort (HS), an internal algorithm with a (n log n) time complexity.
{ Quick-Sort (QS), an internal algorithm with a O(n2) time complexity and
O(n log n) expected time. Here we implemented the standard Hoare's
algorithm with a random selection of the pivot element.
{ Quick-Sort (QS ), an optimized version of the Hoare's algorithm [
All algorithms have been implemented in the C++ programming language and have been compiled with the GNU C++ Compiler 8.3.0, using the optimization options -O2 -fno-guess-branch-probability. The codes of tested algorithms are available at https://github.com/ostafen/Fast-Insertion-Sort. All tests have been performed on a PC with a 3.40 GHz Intel Quad Core i54670 processor, with 6144 KB cache memory, and running Linux Ubuntu 19.04. Running times have been measured with a hardware cycle counter, available on modern CPUs. We tested our algorithms on input arrays with a size n = 2i, with 2 i 20. For each value of n we reported the mean over the running times of 1000 runs.
For each input size n, tests have been performed on arrays of integers and speci cally on random arrays, partially ordered arrays, and reverse order arrays. Random input sequences have been generated with a uniform distribution in the interval [0 : : : 231], using the C++ random number generator. Partially ordered arrays have been obtained by sorting random generated arrays and subsequently executing a number of swaps equal to 1=4 of the input size. Fig. 5 summarizes the overall behaviour of the algorithms for the discussed generation strategies. It turns out that the newly presented algorithms show in all cases a O(n log n) behaviour in practice, outperforming Merge-Sort and HeapSort (which are asymptotically optimal algorithms). Our new solutions are also very competitive against the Quick-Sort algorithm, even for large sizes of the input arrays. It is worth to notice that Fast-Insertion-Sort(h) algorithms show the lowest running times for 2 h 4, while Fast-Insertion-Sort achieves the best performance for c = 5. For small input size arrays, Block-Insertion-Sort obtains good results, and this is why QS? turns out to be the Quick-Sort-based algorithm with the best performances, outperforming the Quick-Sort implementation which uses Insertion-Sort as a subroutine. The recursive algorithm Fast-InsertionSort turns out to be faster than standard Quick-Sort in almost all cases, and the gap turns out to be more sensible for very small and for very large input arrays. In addition, while reverse order arrays represents the Quick-Sort worst case scenario, algortithms in the Fast-Insertion-Sort family mantain their optimal execution time once again, con rming to be among the most fast and exible general purpose sorting alghoritms.
Random Arrays
microseconds nanoseconds milliseconds 32 64 centiseconds
1024 deciseconds 10 16 128 256 512 2048 4096 8192 MS QS QS QS?
BI FIS(h) FIS MS QS QS QS? eBI FIS(h) FIS 16384 32768 65536 131072 262144 524288
1000000
Partially Sorted Arrays nanoseconds microseconds milliseconds 10 16 32 64 centiseconds 128 256 512 2048 4096
8192 1024 deciseconds 0.4 0.2 0.6 0.4 0.2 0.4 0.2 0.6 0.4 0.2 16384 32768 65536 131072 262144 524288 1000000
In this paper we presented a new family of e cient, exible, stable, simple sorting algorithms, named Fast-Insertion-Sort. The algorithms of such a new family generalize the Insertion-Sort algorithm to multiple elements block insertion and achieve an O(n1+") worst-case time complexity, where " = h1 , for h 2 N. Moreover we generalized the basic idea obtaining a recursive algorithm achieving O(n log n) worst case time complexity. We also discussed how to obtain in-place variations of such algorithms by maintaining their main features. From our experimental results it turns out that our solutions are very competitive with the most e ective sorting algorithms, outperforming fast implementations of the Hoare's Quick-Sort algorithm in many practical cases.