Insertion sort is a simple sorting algorithm that works by repeatedly inserting an element into its correct position in an already sorted array. It’s efficient for small datasets and can be a good choice when the array is nearly sorted.
How Insertion Sort Works
- Start with the second element: The first element is considered sorted.
- Compare and insert: Pick the next element and compare it with the elements in the sorted part of the array.
- Shift elements: If the current element is smaller than the compared element, shift the compared element and all elements after it one position to the right.
- Insert: Insert the current element into the empty position.
- Repeat: Repeat steps 2-4 for all remaining elements in the array.
Visual Example
Let’s sort the array [5, 2, 4, 6, 1, 3] using insertion sort:
Step 1: The first element (5) is considered sorted.
Step 2: Compare 2 with 5. 2 is smaller, so shift 5 to the right and insert 2 in its place.
- Array:
[2, 5, 4, 6, 1, 3]
Step 3: Compare 4 with 5. 4 is smaller, so shift 5 to the right and insert 4 in its place.
- Array:
[2, 4, 5, 6, 1, 3]
Step 4: Compare 6 with 5. 6 is larger, so it remains in its position.
- Array:
[2, 4, 5, 6, 1, 3]
Step 5: Compare 1 with 5. 1 is smaller, so shift 5, 6, and 3 to the right and insert 1 in its place.
- Array:
[1, 2, 4, 5, 6, 3]
Step 6: Compare 3 with 5. 3 is smaller, so shift 5 and 6 to the right and insert 3 in its place.
- Array:
[1, 2, 3, 4, 5, 6]
The array is now sorted.
Code Implementation (Python)
def insertion_sort(arr):
n = len(arr)
# Traverse through 1 to n
for i in range(1, n):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# Driver code to test above
arr = [5, 2, 4, 6, 1, 3]
insertion_sort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print(arr[i], end=" ")
Time Complexity
- Best case: The array is already sorted. The time complexity is O(n).
- Average case: The time complexity is O(n^2).
- Worst case: The array is sorted in reverse order. The time complexity is O(n^2).
Space Complexity
The space complexity of insertion sort is O(1) as it only requires a constant amount of extra space.
Advantages of Insertion Sort
- Simple to implement: Insertion sort is easy to understand and code.
- Efficient for small datasets: It’s a good choice for small arrays.
- Online algorithm: It can process elements one at a time as they arrive.
- Stable: It preserves the relative order of elements with equal keys.
Disadvantages of Insertion Sort
- Inefficient for large datasets: It’s not suitable for large arrays due to its quadratic time complexity.
- Slow for nearly sorted arrays: While it’s efficient for sorted arrays, it can be slow for nearly sorted arrays.
Conclusion
Insertion sort is a basic sorting algorithm that’s suitable for small datasets and simple applications. However, for larger datasets, more efficient algorithms like quicksort or merge sort are preferred. Understanding insertion sort is a good starting point for learning more complex sorting algorithms.
