Insertion Sort

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 compared to more advanced algorithms like quicksort or mergesort, but it performs well for small data sets or partially sorted lists.

Algorithm

The algorithm works by iterating through the array and repeatedly inserting the current element into its correct position within the sorted portion of the array. The sorted portion starts with a single element at index 0 and gradually expands as more elements are inserted.

Here's how the insertion sort algorithm works:

      function insertionSort(arr) {
        for (let i = 1; i < arr.length; i++) {
          let current = arr[i];
          let j = i - 1;

          while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
          }

          arr[j + 1] = current;
        }

        return arr;
      }
    

Explanation:

• Initialize a for loop to iterate over each element of the array, starting from the second element (i = 1).
• Inside the loop:
  • Assign the current element arr[i] to the variable current.
  • Set j to i - 1.
  • Enter a while loop that continues as long as j is greater than or equal to 0 and the element at arr[j] is greater than current.
  • Within the while loop:
    • Shift the element at arr[j] one position to the right by assigning arr[j + 1] = arr[j].
    • Decrement j by 1 to continue checking previous elements.
  • Once the while loop terminates, assign current to arr[j + 1], placing the current element in its correct position.
• The for loop continues to the next iteration, repeating the above steps until all elements are sorted.
• Finally, return the sorted arr array.

Example

Let's say we have an array of numbers: [5, 2, 4, 6, 1, 3]. We start with the second element (index 1) and compare it with the previous element. If the previous element is greater, we shift it to the right, making space for the current element. We continue this process until we find the correct position for the current element.

      
        Initial array: [5, 2, 4, 6, 1, 3]

        Step 1: [2, 5, 4, 6, 1, 3]
        Step 2: [2, 4, 5, 6, 1, 3]
        Step 3: [2, 4, 5, 6, 1, 3]
        Step 4: [1, 2, 4, 5, 6, 3]
        Step 5: [1, 2, 3, 4, 5, 6]
      
    

Complexity

The worst-case time complexity of insertion sort is O(n^2), where n is the number of elements in the array. This occurs when the array is sorted in reverse order. However, the best-case time complexity is O(n) when the array is already sorted. The space complexity of insertion sort is O(1) since it only requires a constant amount of additional memory.

Conclusion

Insertion Sort is a simple and intuitive sorting algorithm. While it may not be the most efficient for large datasets, it can be useful for small lists or partially sorted arrays. Understanding the basics of insertion sort can provide a foundation for learning more complex sorting algorithms.

---