How To Do Insertion Sort in JavaScript

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!

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:

1. The first element is considered sorted.
2. The second element (11) is compared with the first (12) and inserted before it.
3. The third element (13) is larger than the sorted portion and remains in place.
4. The fourth element (5) is smaller than all previous elements and is inserted at the beginning.
5. 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:

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

Cons:

1. Inefficient for Large Arrays: Its O(n²) time complexity makes it inefficient for large datasets compared to algorithms like QuickSort or MergeSort.
2. 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:

1. Small Arrays: When working with small arrays (e.g., fewer than 20 elements), the simplicity of Insertion Sort makes it a reasonable choice.
2. Nearly Sorted Arrays: Insertion Sort performs exceptionally well on nearly sorted arrays, where it can achieve close to O(n) time complexity.
3. 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!