Insertion Sort: A Simple Yet Efficient Sorting Algorithm

Insertion Sort is another fundamental sorting algorithm that is intuitive and easy to implement. It works similarly to how you might sort playing cards in your hands: by building a sorted section of the array one element at a time. In this article, I’ll explore how Insertion Sort works, provide a detailed implementation, and discuss its time and space complexity.

How Insertion Sort Works

Insertion Sort builds the final sorted array one element at a time. It iterates through the array, picking one element and inserting it into its correct position within the already sorted portion of the array.

Key Concepts

1. Incremental Sorting: Insertion Sort progressively sorts the array by inserting each new element into its correct position relative to the already sorted portion.
2. Shifting Elements: As each element is inserted, other elements in the sorted portion are shifted to make room.
3. Efficient for Small or Nearly Sorted Data: Insertion Sort is particularly efficient for small datasets or arrays that are already nearly sorted.

For a visual representation of how Insertion Sort operates, check out this video.

Implementation

Here’s a TypeScript implementation of Insertion Sort:

export const insertionSort = (array: number[]): number[] => {
  for (let j = 1; j < array.length; j++) {
    const element = array[j];
    let i: number;
    // Find the correct position for element
    for (i = j - 1; i >= 0 && array[i] > element; i--) {
      // Shift elements to the right
      array[i + 1] = array[i];
    }
    // Insert the element into its correct position
    array[i + 1] = element;
  }
  return array;
};

Disclaimer: Please note that the following implementation modifies the input array directly to sort the elements in place. If you need to retain the original array, consider creating a copy before applying the sort.

Explanation of the Implementation

1. Outer Loop: The outer loop starts from the second element (index 1) and iterates through the array. The first element is considered the initial sorted portion.
2. Inner Loop: The inner loop searches for the correct position for the current element by comparing it with elements in the sorted portion of the array.
3. Shifting and Inserting: If an element in the sorted portion is larger than the current element, it is shifted one position to the right to make space for the current element. Once the correct position is found, the element is inserted.

Time and Space Complexity

Time Complexity

• Worst-case: O(n²) => This occurs when the array is in reverse order, requiring every element to be compared and shifted.
• Best-case: O(n) => This occurs when the array is already sorted. The algorithm simply iterates through the array without making any shifts.
• Average-case: O(n²) => On average, the algorithm performs O(n²) comparisons and shifts.

Space Complexity

• Space Complexity: O(1) => Insertion Sort is an in-place sorting algorithm, requiring only a constant amount of additional memory space.

Further Reading

For more insights into sorting algorithms, explore our detailed articles on other classic algorithms:

• Bubble Sort: Understand how this algorithm repeatedly compares and swaps adjacent elements.
• Selection Sort: Learn about finding and placing the minimum element in its correct position.
• Quick Sort: Discover the efficiency of Quick Sort’s divide-and-conquer approach.
• Merge Sort: Explore how Merge Sort divides and merges arrays to achieve sorted order.

Conclusion

Insertion Sort is a simple yet effective algorithm, particularly useful for small datasets or when the array is nearly sorted. It provides a clear and intuitive approach to sorting by inserting elements into their correct positions.

Whether you’re learning sorting algorithms for the first time or reviewing fundamental concepts, Insertion Sort is a great algorithm to start with, offering both simplicity and insight into the mechanics of sorting.