Insertion Sort Algorithm

Insertion Sort is a simple comparison-based sorting algorithm. It builds the final sorted array one item at a time by continuously taking the next element and inserting it into its correct position within the already sorted part of the array.

How Insertion Sort Works

1. Divide the Array:

   • Divide the array into two subarrays: sorted and unsorted.

2. Iterative Sorting:

   • Iterate through the unsorted subarray, taking one element at a time.

3. Insertion Process:

   • Compare the current element with elements in the sorted subarray.
   • Shift the greater elements one position up to make space for the current element.
   • Insert the current element into the correct position in the sorted subarray.

4. Repeat Until Sorted:

   • Continue this process until the entire array is sorted.

Key Features

• Simple Implementation: Insertion Sort is simple to implement and efficient for small datasets.

• In-Place Sorting: It sorts the elements within the original array without requiring additional memory.

Efficiency

• Time Complexity: The average and worst-case time complexity of Insertion Sort is O(n^2), where n is the number of elements.

• Space Complexity: Insertion Sort has a space complexity of O(1) as it sorts elements in place.

Advantages of Insertion Sort

Insertion Sort has several advantages, including:

• Simple Implementation: It is straightforward to implement and understand.
• Efficient for Small Arrays: Performs well with small datasets or partially sorted lists.
• In-Place Sorting: It sorts elements within the original array without requiring additional memory.

Disadvantages of Insertion Sort

Insertion Sort also has some limitations, such as:

• Inefficient for Large Datasets: It performs poorly with larger, unsorted arrays.
• Quadratic Time Complexity: Has a time complexity of O(n^2), which makes it unsuitable for larger lists.

Insertion Sort Implementation in JavaScript

Here's an example of Insertion Sort implemented in JavaScript:

function insertionSort(arr) {
    const n = arr.length;
    for (let i = 1; i < n; i++) {
        let key = arr[i];
        let j = i - 1;
 
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
}
 
const unsortedArray = [12, 34, 54, 2, 3];
const sortedArray = insertionSort(unsortedArray);
console.log("Sorted Array:", sortedArray);

In this JavaScript code:

• The `insertionSort` function implements the Insertion Sort algorithm.
• It sorts an input array by comparing elements and rearranging them.
• The example usage demonstrates how to use the Insertion Sort function.