Understanding insertion sort algorithm: Beginner's guide with leetcode problems

There are many sorting algorithms 🧮, and each has its own strengths and weaknesses. Some are more efficient for large datasets 📊, while others are simpler and easier to understand 🤓. In this article, we'll explore one of the simplest sorting algorithms, Insertion Sort 📥. We'll look at how it works, its algorithm complexity, and how to implement it in JavaScript and finally solve some LeetCode problems using Insertion Sort 🏆.

I hope you are ready for this? Are you?

Table of Contents

1. Introduction
2. What is an Insertion Sort Algorithm?
3. How does Insertion Sort work?
   • Time Complexity
   • Space Complexity
4. Implementation of Insertion Sort
5. Solving LeetCode Problems
6. Conclusion
7. References

Introduction

Insertion Sort algorithm is a comparison-based sorting algorithm that builds a sorted array one element at a time. It is one of the simplest sorting algorithms and is also known as a stable sort algorithm. It can be used for sorting small data sets or for educational purposes and can be implemented with just a few lines of code.

What is an Insertion Sort Algorithm?

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has advantages such as simple implementation, efficient for small data sets, stable sort, and in-place sorting algorithm.

How does Insertion Sort work?

Imagine we have an array [5, 3, 8, 4, 2] that we want to sort in ascending order using Insertion Sort. Here's how we'll go about it:

1. Start with [5] (first element is considered sorted)
2. Take 3: [5, 3] → [3, 5] (3 is smaller than 5, so we swap them)
3. Take 8: [3, 5, 8] (8 is already in the correct position)
4. Take 4: [3, 5, 8, 4] → [3, 4, 5, 8] (4 is smaller than 8, so we swap them)
5. Take 2: [3, 4, 5, 8, 2] → [2, 3, 4, 5, 8] (2 is smaller than 8, so we swap them)

Final sorted array: [2, 3, 4, 5, 8]

Time Complexity

• Best-case scenario: O(n)
  • Occurs when the array is already sorted
  • The algorithm only needs to do n-1 comparisons
• Average-case scenario: O(n^2)
  • On average, each element must be compared with about half of the previous elements
• Worst-case scenario: O(n^2)
  • Occurs when the array is sorted in reverse order (that is, the array is in descending order and we want to sort it in ascending order)
  • Each element must be compared with all previous elements

Space Complexity

Insertion Sort has a space complexity of O(1) because it sorts the array in-place. It only requires a constant amount of additional memory space regardless of the input size.

Implementation of Insertion Sort

Having understood how Insertion Sort works, let's implement it in JavaScript:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i]; // current element
    let j = i - 1; // index of previous element

    // 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;
}

console.log(insertionSort([5, 3, 8, 4, 2])); // Output: [2, 3, 4, 5, 8]

Let's break down the code:

1. We start with the second element (index 1 from our for-loop) because we consider the first element as already sorted.
2. We store the current element as key.
3. We compare key with the elements before it, moving elements that are greater than key one position ahead.
4. We place key in its correct position in the sorted portion of the array.
5. We repeat this process for all elements in the array.

It is important to note that Insertion Sort is already optimal for small data sets and mostly sorted arrays. However, it becomes inefficient for large, unsorted arrays. In such cases, more advanced algorithms like QuickSort or MergeSort are preferred.

Solving LeetCode Problems

Let's look at a LeetCode problem that can be solved using Insertion Sort:

Problem 1: Sort an Array [Easy]

Problem: You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Approach: We can use a for-loop to traverse the array and insert each element into the correct position in the sorted portion. This is a direct application of insertion sort.

Solution:

function merge(nums1, m, nums2, n) {
  // Step 1: Copy elements from nums2 into nums1
  for (let i = 0; i < n; i++) {
    nums1[m + i] = nums2[i];
  }
  // Step 2: Apply Insertion Sort on the merged nums1 array
  for (let i = 1; i < m + n; i++) {
    let key = nums1[i];
    let j = i - 1;

    // Shift elements of nums1[0..i-1] that are greater than key to one position ahead
    while (j >= 0 && nums1[j] > key) {
      nums1[j + 1] = nums1[j];
      j--;
    }
    nums1[j + 1] = key; // Insert key at the correct position
  }
}

Problem 2: Insertion Sort List [Medium]

Problem: Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

Approach: This problem is a direct application of insertion sort. We can use a dummy node to keep track of the sorted portion of the list and insert each node into the correct position in the sorted portion. We can use a pointer to traverse the list and insert each node into the correct position in the sorted portion.

Solution:

// Function to perform insertion sort on a linked list
const insertionSortList = function (head) {
  // Create a dummy node to simplify insertion at the beginning
  let dummy = new ListNode(0);
  let current = head;

  // Iterate through each node in the original list
  while (current) {
    // Start from the dummy node to find the correct position
    let prev = dummy;

    // Move prev until we find the right position to insert current
    while (prev.next && prev.next.val < current.val) {
      prev = prev.next;
    }

    // Store the next node to process
    let next = current.next;

    // Insert current node into the sorted portion
    current.next = prev.next;
    prev.next = current;

    // Move to the next unsorted node
    current = next;
  }

  // Return the head of the sorted list (excluding dummy node)
  return dummy.next;
};

Noticed how we used while-loop to traverse the list and insert each node into the correct position in the sorted portion. Unlike the array implementation of insertion sort where we used for-loop to traverse the array and insert each element into the correct position in the sorted portion. This is because our data structure is a linked list and not the regular array.

Conclusion

Insertion Sort is a very simple and straightforward sorting algorithm that's especially effective for small arrays or arrays that are already mostly sorted. While it may not be the most efficient choice for large, unsorted datasets, its simplicity makes it a great starting point for understanding sorting algorithms.

Key takeaways:

• Insertion Sort builds the final sorted array one item at a time.
• It's efficient for small datasets and nearly-sorted arrays.
• It has a best-case time complexity of O(n) and a worst-case of O(n^2).
• It sorts in-place, requiring only O(1) additional memory.

Understanding Insertion Sort provides a solid foundation for learning more complex sorting algorithms and helps in solving various coding problems efficiently.

References

• GeeksforGeeks: Insertion Sort
• LeetCode Sorting Problems

Stay Updated and Connected

To ensure you don't miss any part of this series and to connect with me for more in-depth
discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data
structures and algorithms, and other exciting tech topics, follow me on:

Emmanuel Ayinde Follow

Software Engineer | Technical Writer | Backend, Web & Mobile Developer 💻 | Passionate about crafting efficient and scalable software solutions

• GitHub
• Linkedin
• X (Twitter)

Stay tuned and happy coding 👨‍💻🚀