Sorting is a fundamental operation in the field of computer science, and because of this, there are various algorithms available to solve this problem. Each one is chosen based on factors such as the number of items to sort, the degree of order already present, the computer architecture where the algorithm will be executed, the type of storage device, among others. In this article, we will explore the insertion sort algorithm, understanding its nuances, strengths, and limitations.
<h2>What is insertion sort?</h2>
Insertion sort is a comparison-based algorithm that constructs its output one element at a time. It works similarly to the method we use to sort a deck of cards: we take one card at a time, compare it with the ones we already have in our hand, place the card in the correct position, and repeat this action until we finish our deck.
It is an adaptive algorithm, meaning it is efficient for small data sets, as well as other quadratic complexity algorithms (<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2)). It is simple to implement, requires a constant amount of memory, as changes in the list are made in the list itself (without the need to create a new list, which would double the use of memory), and is capable of sorting the list as it receives it.
<h2>How does insertion sort work?</h2>
Initialization: We assume that the first element of our list is already sorted. We proceed to the next element, consider it as our key, and insert it in the correct position in the sorted part of the list;
Iteration: For each item in the list (starting from the second element), we store the current item (key) and its position. Then we compare the key with the elements in the sorted part of the list (elements before the key);
Insertion: If the current element in the sorted part is greater than the key, we move that element one position up. This creates space for the new key to be inserted;
Repositioning the Key: We continue moving elements one position up until we find the correct position for the key. This position is found when we encounter an element that is less than or equal to the key or when we reach the beginning of the list;
Repeat: The process is repeated for all the elements in the list.
<h2>Implementation in JavaScript</h2>
To better understand the algorithm, let&#39;s implement it in JavaScript:
<pre><code class="highlited-code-wrapper langjs"><div class="highlited-code" data-language="js">/**
* Sorts an array of numbers using the insertion sort algorithm.
* 
* @param {number[]} numbers - The list of numbers to be sorted.
* @returns {number[]} - The sorted list of numbers.
*/
function insertionSort(numbers) {
 for (let i = 1; i &lt; numbers.length; i++) {
 const key = numbers[i]
 let j = i - 1
 
 while (j &gt;= 0 &amp;&amp; numbers[j] &gt; key) {
 numbers[j + 1] = numbers[j]
 j--
 }

 numbers[j + 1] = key
 }
}</div>
</code></pre><h2>Complexity Analysis</h2>
<h3>Time Complexity</h3>
Best Case (Array is already sorted): <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>O(n). This is because the inner loop (while) is not executed at all;
Average Case and Worst Case (Array is sorted in reverse order): <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2). In the worst case, each iteration will cause an element to be moved. This makes the algorithm inefficient for large data sets.
<h2>Space Complexity</h2>
Space Complexity: <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1). Insertion sort is an in-place algorithm; it requires a constant amount of memory space.

Mastering Insertion Sort: A Detailed Guide

<h2>What is an Algorithm?</h2>
An algorithm is a precise and unambiguous specification of a sequence of computational steps that can be mechanically performed[^1]. From this, we can think of a function that receives a value or a set of values as input and returns a value or a set of values as its output.
An algorithm can be correct or incorrect. It is correct when, given its input parameters, its output is correct and, therefore, solves the computational problem for which it was developed. An incorrect algorithm, on the other hand, may stop with an incorrect output or may not stop at all for some input instances. Still, some incorrect algorithms can still have useful applications.
There can be different algorithms that solve the same problem, some more efficient, that is, faster than others. But, not every problem has an efficient solution. Such problems are known as <abbr title="Non-deterministic Polynomial time">NP</abbr>-complete.
<abbr title="Non-deterministic Polynomial time">NP</abbr>-complete problems are very interesting: even though no efficient algorithm has been found for this class of problems, it has not been proven that it is not possible to find an efficient algorithm (from class P, which can be solved in polynomial time) for such a problem. Moreover, if there were an efficient algorithm to solve an NP-complete problem, it would mean that there is an efficient algorithm for all <abbr title="Non-deterministic Polynomial time">NP</abbr>-complete problems.
<Alert title="P vs. NP">
P vs. NP is a fundamental question in computer science, specifically in the field of computational complexity theory. It concerns the relationship between two classes of problems. The P class consists of decision problems (problems with a yes or no answer) that can be quickly solved (in polynomial time) by a deterministic computer, meaning that the time needed to solve the problem grows at a manageable rate as the size of the input increases. On the other hand, the NP class consists of decision problems for which, if a solution is provided, it can be quickly verified (also in polynomial time) by a deterministic computer.

The crucial question, &quot;Is P equal to NP?&quot;, asks whether every problem whose solution can be quickly verified (NP) can also be solved quickly (P). This is profound because, if P were equal to NP, it would mean that all the problems that we can verify quickly can also be solved quickly. This has vast implications for various fields, including cryptography, optimization, and algorithm design.
</Alert>
<h2>Algorithmic Complexity</h2>
When we talk about algorithms, most of the time we are interested in the growth rate of time and space required to solve increasingly larger instances of certain problems. If we are interested in the time a particular algorithm takes to perform its function, we are interested in its time complexity. And the behavior of the time complexity limit of our algorithm in relation to the increase of the problem instances is called asymptotic time complexity. And it is this asymptotic complexity that determines the size of the problem that can be solved by algorithms[^2].
If an algorithm takes a time <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">cn^2</annotation></semantics></math>cn2 for a constant <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>c</mi></mrow><annotation encoding="application/x-tex">c</annotation></semantics></math>c to process an input of size <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n, we say that the complexity of the algorithm is of the order of <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">n^2</annotation></semantics></math>n2, or, in Bachmann–Landau notation (also called asymptotic notation and Big O notation), the algorithm has complexity <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math>O(n2).
To get a better idea of what this means in relation to the runtime of our algorithm, consider that one unit of time on the computer on which we run our algorithm is 1 millisecond. Now, we want to know what the maximum size of input that our algorithm can process within a certain time limit (one second, one hour, and one day). Note, in the table below, how much the complexity of the algorithm interferes with the maximum size of the input it can handle, given the time limit:
<table>
<thead>
<tr>
<th>Time Complexity</th>
<th>1 second</th>
<th>1 minute</th>
<th>1 hour</th>
</tr>
</thead>
<tbody><tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n</td>
<td>1000</td>
<td>60000</td>
<td>360000</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><msub><mrow><mi>log</mi><mo>⁡</mo></mrow><mn>2</mn></msub><mi>n</mi></mrow><annotation encoding="application/x-tex">n \log_2 n</annotation></semantics></math>nlog2​n</td>
<td>140</td>
<td>4895</td>
<td>204095</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">n^2</annotation></semantics></math>n2</td>
<td>31</td>
<td>244</td>
<td>1897</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>3</mn></msup></mrow><annotation encoding="application/x-tex">n^3</annotation></semantics></math>n3</td>
<td>10</td>
<td>39</td>
<td>153</td>
</tr>
<tr>
<td><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>n</mi></msup></mrow><annotation encoding="application/x-tex">2^n</annotation></semantics></math>2n</td>
<td>9</td>
<td>15</td>
<td>21</td>
</tr>
</tbody></table>
Even though we can build faster computers, the increase in the execution speed of less efficient algorithms would not be so significant, so we should always seek the most efficient algorithm to address a given problem.
[^1]: AHO, Alfred V.; ULLMAN, Jeffrey D. Foundations of Computer Science. Stanford, 1994.
[^2]: AHO, Alfred V.; HOPCROFT, John E.; ULLMAN, Jeffrey D. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.

Douglas Moura

Douglas Moura

#algorithms

Mastering Insertion Sort: A Detailed Guide

Introduction to algorithms

Understanding Tail Call Optimization With JavaScript