Top of the day, my dear coders! I hope you are all having a beautiful day. Welcome to another chapter of the Sorting algorithms with JavaScript series. Today we are talking about the Insertion Sort algorithm!

The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. - Donald Knuth

Let's dive in! 🤿

Insertion sort algorithm solves the sorting problem:
Input: A sequence of n numbers
Output: A permutation (reordering) of the input sequence

The numbers that we want to sort, are also known as keys. Input is usually an array of n elements.

Insertion sort algorithm is an efficient algorithm for sorting a small number of elements.

Insertion sort works the way many people sort a hand of playing cards.

STEPS

1. We start with an empty left hand and the cards face down on the table.
2. We remove one card at a time from the table and insert it into the correct position in the left hand.
3. To find the correct position for a card, we compare it with each of the cards already in the hand (right to left)
4. At all times, the cards held in the left hand are sorted, and these cards were originally the top cards of the pile on the table

In this chapter, I will also introduce you to pseudocode. Pseudocode is an artificial and informal language that helps us programmers develop algorithms. Pseudocode is a "text-based" detail (algorithmic) design tool. The rules of Pseudocode are reasonably straightforward.

We will call this pseudocode (procedure) INSERTION-SORT-ALGO. It will take an array A[1...n], that contains a sequence of length n that is to be sorted. This procedure will rearrange the numbers within array A, with at most a constant number of them stored outside the array at any time.

INSERTION-SORT-ALGO(A: array)
1 for j = 2 to A.length
2   key = A[j]
3   //Insert A[j] into the sorted sequence A[1...j-1]
4   i = j - 1
5   while i > 0 and A[i] > key
6      A[i+1] = A[i]
7      i = i - 1
8   A[i+1] = key

Let's say that our array A looks like this: [9, 5, 6, 12];
The iteration of the loop starting at 1 and ending at 8, in each iteration, the black rectangle holds the key taken from A[j] which is compared to its left-hand side elements.

Let's see an implementation, but we will work with a larger dataset. For example, let our array be: [5, 9, 6, 12, 1, 2, 34, 15, 7]

Play with the code! 🕺🏻

References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me!