## Introduction

Sorting algorithms are fundamental in computer science, and **Insertion Sort** is one of the simplest to understand and implement. It is often used for small datasets or as a part of more complex algorithms like TimSort. This blog post will cover how to implement Insertion Sort in JavaScript, its time and space complexities, and when it is most useful.

**What is Insertion Sort?**

**Insertion Sort** works similarly to the way you might sort a hand of playing cards. You pick one card at a time and place it in the correct position relative to the cards already sorted. The array is conceptually split into two parts: the sorted and unsorted sections. The algorithm picks one element from the unsorted part and inserts it into its correct position in the sorted part.

Below is our visualization tool to see **Insertion Sort** in real-time!

**Why start at index 1?**

Insertion Sort works by assuming the first element is already sorted (since a single element is trivially sorted). Therefore, the algorithm starts at index 1 and compares the element at that index with the previous ones, inserting it into its correct position in the sorted portion of the array.

**Pseudocode for Insertion Sort**

Here’s the step-by-step pseudocode for Insertion Sort:

procedure insertionSort(arr) for i = 1 to length(arr) - 1 do key = arr[i] j = i - 1 while j >= 0 and arr[j] > key do arr[j + 1] = arr[j] j = j - 1 arr[j + 1] = key

**Step-by-Step Explanation**:

- You iterate through the array starting from the second element (index 1).
- Each element is compared with the elements before it and is inserted into its correct position in the sorted portion of the array.
- The process continues until all elements are sorted.

**Time Complexity of Insertion Sort**

**Best Case**: O(n) – This occurs when the input array is already sorted. In this case, Insertion Sort only needs to make a single pass through the array.**Average Case**: O(n²) – On average, the algorithm needs to compare and shift elements, leading to quadratic time complexity.**Worst Case**: O(n²) – The worst-case scenario occurs when the array is sorted in reverse order, requiring maximum comparisons and shifts.

**Space Complexity of Insertion Sort**

**Space Complexity**: O(1) – Insertion Sort is an in-place sorting algorithm, meaning it sorts the array without requiring any additional memory allocation.

**JavaScript Implementation of Insertion Sort**

Here’s how you can implement Insertion Sort in JavaScript:

function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; let j = i - 1; // Move elements of arr[0..i-1], that are greater than key, to one position ahead // of their current position while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } return arr; } // Example usage with a larger array: const arr = [12, 11, 13, 5, 6]; console.log("Initial array:", arr); const sortedArray = insertionSort(arr); console.log("Sorted array:", sortedArray);

**Output:**

Initial array: [ 12, 11, 13, 5, 6 ] Sorted array: [ 5, 6, 11, 12, 13 ]

**Explanation**:

- The outer loop picks one element (
`key`

) starting from the second element of the array. - The inner
`while`

loop shifts elements that are greater than`key`

one position to the right. - Once the correct position is found, the
`key`

is inserted into its place, ensuring that the left part of the array is always sorted.

We will explain how **Insertion Sort** processes this array element by element and places each element into its correct position in the sorted portion of the array.

**Step-by-Step Walkthrough**

**Step 1: First Element (12)**

- The first element is already sorted, so nothing needs to be done.
**Array after step 1**:`[12, 11, 13, 5, 6]`

**Step 2: Second Element (11)**

- We compare
`11`

with`12`

. Since`11 < 12`

, we shift`12`

one position to the right and insert`11`

at the beginning. **Array after step 2**:`[11, 12, 13, 5, 6]`

**Step 3: Third Element (13)**

- We compare
`13`

with`12`

. Since`13 > 12`

, it is already in the correct position. **Array after step 3**:`[11, 12, 13, 5, 6]`

**Step 4: Fourth Element (5)**

- We compare
`5`

with`13`

,`12`

, and`11`

. Since`5 < 11`

, we shift`13`

,`12`

, and`11`

one position to the right and insert`5`

at the beginning. **Array after step 4**:`[5, 11, 12, 13, 6]`

**Step 5: Fifth Element (6)**

- We compare
`6`

with`13`

,`12`

, and`11`

. Since`6 < 11`

, we shift`13`

,`12`

, and`11`

one position to the right and insert`6`

in its correct position between`5`

and`11`

. **Array after step 5**:`[5, 6, 11, 12, 13]`

**Final Sorted Array**

After all the steps are complete, the final sorted array is:

[5, 6, 11, 12, 13]

**Summary of Steps**:

- The first element is considered sorted.
- The second element (
`11`

) is compared with the first (`12`

) and inserted before it. - The third element (
`13`

) is larger than the sorted portion and remains in place. - The fourth element (
`5`

) is smaller than all previous elements and is inserted at the beginning. - The fifth element (
`6`

) is inserted between`5`

and`11`

, completing the sorting process.

This process is repeated until the entire array is sorted. Insertion Sort works well for small datasets or nearly sorted arrays, as seen here.

**Pros and Cons of Using Insertion Sort**

**Pros**:

**Simplicity**: Insertion Sort is easy to understand and implement.**Efficient for Small Arrays**: It performs well on small datasets or nearly sorted arrays.**Stable Sorting**: It preserves the relative order of equal elements, making it a stable sorting algorithm.**In-Place Sorting**: Insertion Sort uses constant additional memory (O(1)).

**Cons**:

**Inefficient for Large Arrays**: Its O(n²) time complexity makes it inefficient for large datasets compared to algorithms like QuickSort or MergeSort.**More Comparisons and Shifts**: In the worst case, Insertion Sort performs a high number of comparisons and shifts.

**When to Use Insertion Sort**

Insertion Sort is typically used in the following scenarios:

**Small Arrays**: When working with small arrays (e.g., fewer than 20 elements), the simplicity of Insertion Sort makes it a reasonable choice.**Nearly Sorted Arrays**: Insertion Sort performs exceptionally well on nearly sorted arrays, where it can achieve close to O(n) time complexity.**Part of a Hybrid Sorting Algorithm**: Insertion Sort is often used as a subroutine in more efficient sorting algorithms like**TimSort**and**IntroSort**, where it is employed to handle small partitions.

**Comparison with Other Sorting Algorithms**

Insertion Sort is a basic sorting algorithm that works best on small or nearly sorted datasets. It is often compared with **Bubble Sort** and **Selection Sort**. Unlike Bubble Sort, Insertion Sort minimizes unnecessary swaps, and it is generally faster than Selection Sort for small datasets because it stops early if the array is nearly sorted.

**Conclusion**

**Insertion Sort** is a simple and intuitive algorithm, making it an excellent choice for small or nearly sorted datasets. While it’s not suitable for large datasets due to its O(n²) time complexity, it is still an important algorithm to learn. Its role in hybrid algorithms like **TimSort** highlights its practical utility for optimizing the performance of complex sorting operations.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Insertion Sort:

In Python – How to do Insertion Sort in Python

In C++ – How to Do Insertion Sort in C++

In Rust – How to do Insertion Sort in Rust

In Java – How to do Insertion Sort in Java

Have fun and happy researching!

Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.