A Voyage through Algorithms using Javascript - Insertion Sort

What is Insertion Sort?

Insertion Sort is another fundamental sorting algorithm in computer science. It builds the final sorted array one item at a time. It's much like sorting a hand of playing cards - you pick up cards one by one and insert each into its proper position among the cards you've already sorted.

How Insertion Sort Works

Insertion Sort iterates through the array, growing the sorted portion with each iteration. For each element, it compares it with the already sorted elements, moving them up until it finds the correct position to insert the current element.

Here's a step-by-step breakdown:

1. Start with the second element (index 1) as the "current" element.
2. Compare the current element with the one before it.
3. If the current element is smaller, compare it with the elements before. Move the greater elements up to make space for the swapped element.
4. Repeat steps 2-3 until the whole array is sorted.

Visualization of Insertion Sort:

Recorded gif from https://visualgo.net/en/sorting

Implementing Insertion Sort in JavaScript

Let's take a look at the implementation of Insertion Sort in JavaScript, with detailed comments explaining each part:

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

Key Points:

1. Two-Directional Process: Insertion Sort operates through a forward-moving outer loop and a backward-looking inner loop, creating a back-and-forth movement that forms the core of the algorithm.
2. Forward Scan (Outer Loop):

   for (let i = 1; i < arr.length; i++)

Moves forward through the array, selecting one unsorted element (currentElement = arr[i]) at a time.

1. Backward Insert (Inner Loop):

   while (j >= 0 && arr[j] > currentElement)

Looks backward into the sorted portion, shifting larger elements right (arr[j + 1] = arr[j]) to make room for the current element.

1. Element Insertion:

   arr[j + 1] = currentElement;

Inserts the current element into its correct position, growing the sorted portion.

1. In-Place and Stable Sorting: Modifies the original array directly, maintaining the relative order of equal elements.

Insertion Sort builds the final sorted array one item at a time, mimicking how you'd sort a hand of cards. It repeatedly selects a card (element) from the unsorted portion and inserts it into its correct position among the sorted cards, shifting larger cards as needed. This intuitive process makes Insertion Sort efficient for small or nearly-sorted datasets.

Is Insertion Sort Stable?

Yes, Insertion Sort is a stable sorting algorithm. Stability in sorting algorithms means that the relative order of equal elements is preserved after sorting. Insertion Sort achieves this naturally due to its method of operation:

1. Preserving Order: When inserting an element into the sorted portion, Insertion Sort only shifts elements that are strictly greater than the current element. This means that if there are multiple elements with the same value, their relative order will be maintained.
2. No Unnecessary Swaps: Unlike some other sorting algorithms that might swap equal elements, Insertion Sort only moves an element when necessary. This characteristic ensures that equal elements remain in their original relative positions.
3. Left-to-Right Processing: By processing the array from left to right and inserting each element into its correct position among the already-sorted elements, Insertion Sort naturally maintains the original order of equal elements.

The stability of Insertion Sort can be particularly useful when sorting complex data structures where maintaining the original order of equal elements is important. For example, when sorting a list of students first by grade and then by name, a stable sort would ensure that students with the same grade remain in alphabetical order by name.

This stability is an inherent property of the basic Insertion Sort algorithm and doesn't require any additional modifications or overhead to achieve, making it a naturally stable sorting method.

Time and Space Complexity Analysis

Insertion Sort's performance characteristics are as follows:

• Time Complexity:

  • Best Case: O(n) - when the array is already sorted
  • Average Case: O(n^2)
  • Worst Case: O(n^2) - when the array is reverse sorted

• Space Complexity: O(1) - Insertion Sort is an in-place sorting algorithm

Unlike Selection Sort, Insertion Sort can perform well on nearly sorted arrays, achieving close to linear time complexity in such cases.

Advantages and Disadvantages of Insertion Sort

Advantages:

• Simple to implement and understand
• Efficient for small to medium-sized datasets
• Adaptive - performs well on nearly sorted arrays
• Stable - maintains relative order of equal elements
• In-place sorting (O(1) space)
• Suitable for online sorting scenarios

Disadvantages:

• Inefficient for large datasets (O(n^2) in average and worst cases)
• Performance degrades quickly as input size increases

When to Use Insertion Sort

• Small to medium-sized datasets (generally up to a few hundred elements)
• Nearly sorted data
• Online sorting scenarios where elements are received and sorted incrementally
• As a subroutine in more complex algorithms (e.g., Quicksort for small partitions)

Practical Applications and Use Cases

1. Standard library implementations: Often used for small arrays or as part of hybrid sorting algorithms
2. Database operations: Sorting small sets of records
3. Embedded systems: Suitable for systems with limited resources due to its simplicity and low memory overhead
4. Real-time data processing: Maintaining sorted order as data is received

Conclusion

Insertion Sort, despite its limitations for large datasets, offers valuable advantages in specific scenarios. Its intuitive nature, resembling how we might sort cards by hand, makes it an excellent educational tool for understanding sorting algorithms.

Key takeaways:

• Best-case time complexity of O(n) for nearly sorted data
• Stable, in-place, and adaptive sorting algorithm
• Efficient for small datasets and online sorting
• Often incorporated into hybrid sorting strategies

While not suitable for large-scale sorting tasks, Insertion Sort's principles are often applied in more sophisticated methods. Its simplicity and efficiency in certain scenarios make it a valuable addition to a programmer's algorithmic toolkit.

The choice of sorting algorithm ultimately depends on your specific use case, data characteristics, and system constraints. Understanding Insertion Sort provides insights into algorithm design trade-offs and lays a foundation for exploring more advanced sorting techniques.