An Introduction to Insertion Sort: Sorting Tutorials

In this article, we’re going to explore insertion sort – a popular, simple sorting algorithm for handling array data.

Knowing the insertion sort algorithm will not only improve your computer science knowledge in general, but is a fantastic sorting method when it comes to small sets of array data – especially compared to many other sorting methods available.

Let’s dive in and explore insertion sort!

Table of contents

Overview

Sooner or later, a coding project will require an array to be sorted (and an array with more than only one element). Whether it be a list of strings that need to be sorted in alphabetical order or an array of integers that need to be arranged from largest to smallest, sorting problems occur frequently.

One of the algorithms commonly used for sorting an array is an “Insertion Sort” algorithm. In the simplest of terms, an insertion sort algorithm divides a list into “sorted” and “unsorted” parts. The algorithm starts at one end of the list (usually the first element) and deems that entry as “sorted.” This makes the rest of the entries “unsorted.”

To sort the “unsorted” portion, the algorithm moves along the array (from the second element to the third element, and so forth) and insertion sort compares each current element it’s on with the previous element. In this way, the algorithm “inserts” the unsorted element into its proper place/correct position. In a sense, it’s one-dimensional. The algorithm moves in only one direction along the array to each “new” element in the array.

Examples

Implementing an insertion sort algorithm requires only a few lines of code. Here is an example in Python that sorts numbers in an array from smallest to largest:

def insertionSortAlgorithm(arr):

    for i in range (1, len(arr)):

        #We grab the current entry

        current = arr[i]

        #and grab the index of its predecessor

        j = i-1

        while j >= 0 and arr[j] > current:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = current

Notice that we start at the second entry (the entry with index 1) for this insertion sort code. This is because, at the start of the algorithm, the first entry is considered “sorted” for the purposes of our sorted array. However, as the algorithm checks entries, it may find that this first entry isn’t sorted and needs to be moved around.

We use a while loop to order the other elements. The while loop, first off, makes sure that the algorithm doesn’t go beyond the start of the list (with the “j >= 1” term). Then it checks if the previous entry is greater than the next element immediately after it. If it is, then it places the previous entry above its successor. If it isn’t, it moves backward through the array elements until it finds an entry smaller than it.

Once the loop works through all the elements in the input array, the loop can exit and proceed with the rest of the program after it processes the last element. What the program does after that is up to you – though in our example we’ll simply print our insertion sort array after everything has been put into the correct position.

Let’s implement this algorithm with an unsorted array in no particular order:

array = [91,13,586,1,4,8,92,99,65,782,85,85]

insertionSortAlgorithm(array)

print(array)

When run, the program outputs the following array as the sorted order in ascending order. Note that in our example, we overwrite the value of the initial array with everything in its sorted position:

[1, 4, 8, 13, 65, 85, 85, 91, 92, 99, 586, 782]

When it comes to efficiency, insertion sort algorithms are most efficient on smaller arrays. Sorting large arrays is not ideal because the algorithm has to compare each entry of the array with its predecessors. This means the larger the array, the larger the number of comparisons, and the larger time complexity. However, this only makes insertion sort algorithms inefficient with regard to time. With regards to memory, the insertion sort algorithm is usually efficient because its memory usage stays constant.

An insertion sort algorithm is quick and simple to set up. This makes it one of the most common sorting algorithms implemented in coding projects. It is also one of the best sorting algorithms to use on arrays that are continually growing or changing size. This is because of its simplistic and straightforward logic that only needs to know about an entry’s predecessors to sort each element in the array.

That being said, there are more sorting algorithms available, such as merge sort and selection sort, which are worth checking out. However, insertion sort implementation is an easy place to start, as insertion sort performs intuitively regardless of the kinds of data sets you use.