Insertion Sort in Python

Insertion Sort is very simple and very intuitive sorting algorithm similar to how one arranges playing cards in one’s hand. This algorithm builds the final sorted array one at a time. When working with small datasets and partially sorted data, this algorithm is good, though it is not as efficient on larger datasets.

Here’s a detailed explanation of how Insertion Sort works:

Algorithm

1. Divide the list into two parts:
   • The sorted part (initially contains the first element only).
   • The unsorted part (contains the rest of the elements).
2. Pick the first element from the unsorted part and compare it backward with the elements of the sorted part.
3. Insert the picked element into its correct position in the sorted part by shifting larger elements one position to the right.
4. Repeat this until all elements from the unsorted part get included into the sorted part.

Steps with Example

Let’s sort the array [5, 3, 8, 6, 2]:

1. Initial Array: [5, 3, 8, 6, 2]:
   • The sorted part: [5]
   • The unsorted part: [3, 8, 6, 2]
2. Step 1:
   • Choose 3 from the unsorted part.
   • Compare 3 with 5 in the sorted part. Since 3 < 5, shift 5 to the right.
   • Insert 3 in the first position.
   • Array becomes: [3, 5, 8, 6, 2]
3. Step 2:
   • Choose 8.
   • Compare 8 with 5. Since 8 > 5, it is already in the right place.
   • Array stays: [3, 5, 8, 6, 2]
4. Step 3:
   • Select 6.
   • Compare 6 with 8. Since 6 < 8, move 8 one position to the right.
   • Compare 6 with 5. Since 6 > 5, place 6 after 5.
   • Array becomes: [3, 5, 6, 8, 2]
5. Step 4:
   • Select 2.
   • Compare 2 with 8, 6, 5, and 3. Since 2 < all, shift them all to the right.
   • Insert 2 in the first position.
   • Array becomes: [2, 3, 5, 6, 8]

Python Implementation

Here’s how Insertion Sort can be implemented in Python:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]  # The element to be inserted
        j = i - 1     # Index of the last element in the sorted part

        # Move elements of the sorted part that are greater than the key
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert the key into the correct position
        arr[j + 1] = key

    return arr

# Example usage
numbers = [5, 3, 8, 6, 2]
sorted_numbers = insertion_sort(numbers)
print("Sorted Array:", sorted_numbers)

Explanation of Code

1. Outer Loop: Runs for each element starting from the second element (i = 1).
2. Key: current element to insert in the already sorted portion of the array.
3. Inner Loop: Shifts elements of the sorted part that are greater than the key to the right.
4. Insertion: Positioning the key into its corresponding location.

Time Complexity

1. Best Case: O(n) when the array is already sorted.
2. Worst Case: O(n^2) when the array is sorted in reverse order.
3. Average Case: O(n^2).

Space Complexity

• Insertion Sort is in-place, so the space complexity is O(1).

Advantages

• Simple and easy to implement.
• Efficient for small datasets or partially sorted data.

Disadvantages

• Not suitable for large datasets due to its O(n^2) time complexity.