Insertion Sort

What is Insertion Sort?

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Explanation of the Insertion Sort Algorithm

The insertion sort algorithm works by iterating through an array and, for each element, inserting it into its correct position within the already sorted portion of the array. It builds the sorted array one element at a time.

Step-by-Step Example

Let's consider the array: [5, 2, 4, 6, 1, 3]

1. Initial Array: [5, 2, 4, 6, 1, 3]. Consider the first element (5) as already sorted (a single element is always sorted).
2. Iteration 1: Take the second element (2). Compare it with the element in the sorted part (5). Since 2 < 5, shift 5 to the right and insert 2 in its place. Array becomes: [2, 5, 4, 6, 1, 3]
3. Iteration 2: Take the third element (4). Compare it with the sorted part (2, 5). Since 4 > 2, but 4 < 5, shift 5 to the right and insert 4 in its place. Array becomes: [2, 4, 5, 6, 1, 3]
4. Iteration 3: Take the fourth element (6). Compare it with the sorted part (2, 4, 5). Since 6 is greater than all elements in the sorted part, it remains in its position. Array becomes: [2, 4, 5, 6, 1, 3]
5. Iteration 4: Take the fifth element (1). Compare it with the sorted part (2, 4, 5, 6). Since 1 is smaller than all elements in the sorted part, shift all elements to the right until the beginning of the sorted portion and insert 1 in its place. Array becomes: [1, 2, 4, 5, 6, 3]
6. Iteration 5: Take the sixth element (3). Compare it with the sorted part (1, 2, 4, 5, 6). Since 3 > 2, but 3 < 4, shift 4,5,6 to the right and insert 3 in its place. Array becomes: [1, 2, 3, 4, 5, 6]

The array is now sorted: [1, 2, 3, 4, 5, 6]

Pseudocode

 function insertionSort(array):
        for i from 1 to length(array) - 1:
            key = array[i]
            j = i - 1
            while j >= 0 and array[j] > key:
                array[j + 1] = array[j]
                j = j - 1
            array[j + 1] = key
        return array 

Time and Space Complexity Analysis

Time Complexity

• Best Case: O(n). This occurs when the array is already sorted. Only one comparison is made for each element.
• Average Case: O(n²). On average, each element needs to be compared with half of the already sorted elements.
• Worst Case: O(n²). This occurs when the array is sorted in reverse order. Each element needs to be compared with all of the already sorted elements.

Space Complexity

• Space Complexity: O(1). Insertion sort is an in-place sorting algorithm, meaning it requires a constant amount of extra space regardless of the input size. It only uses a few extra variables for comparison and shifting.

Advantages of Insertion Sort

• Simple to implement: The algorithm is easy to understand and implement.
• Efficient for small datasets: Performs well when sorting small arrays.
• Adaptive: Efficient for data sets that are already substantially sorted. If the input array is partially sorted, insertion sort performs well.
• In-place: Requires minimal extra memory space.
• Stable: Maintains the relative order of elements with equal values.
• Online: Can sort a list as it receives it.

Disadvantages of Insertion Sort

• Inefficient for large datasets: Its quadratic time complexity makes it unsuitable for sorting large arrays.
• Performance degrades as input size increases: The number of comparisons and shifts increase significantly with larger inputs.