Understanding Insertion Sort
Note: this page has been created with the use of AI. Please take caution, and note that the content of this page does not necessarily reflect the opinion of Cratecode.
Ever tried organizing a hand of cards? You probably used a method similar to insertion sort without even knowing it! In this article, we'll dive into the depths of the insertion sort algorithm. By the end, you'll know how it works, how to implement it, and why it might be your goto for small datasets.
What is Insertion Sort?
Insertion sort is a simple and intuitive sorting algorithm. It's akin to sorting playing cards in your hands. You pick one card at a time and insert it into its correct position relative to the cards already in your hand. This ensures that your hand remains sorted at all times.
How Insertion Sort Works
Let's break down the steps of insertion sort:
 Start with the second element: Assume the first element is already sorted.
 Pick the next element: Compare it with the elements in the sorted portion.
 Shift elements: Move the sorted elements one position to the right if they are greater than the current element.
 Insert: Place the current element in its correct position.
 Repeat: Continue until all elements are sorted.
Here's a more detailed visual example using an array:
Suppose we have an array: [4, 3, 2, 10, 12, 1, 5, 6]
.

First Pass:
 Compare
3
with4
. Since3
is smaller, shift4
to the right and insert3
at the beginning.  Array:
[3, 4, 2, 10, 12, 1, 5, 6]
 Compare

Second Pass:
 Compare
2
with4
(and3
). Shift4
and3
to the right and insert2
at the beginning.  Array:
[2, 3, 4, 10, 12, 1, 5, 6]
 Compare

Third Pass:
 Compare
10
with4
. No shifting needed, as10
is already in the correct position.  Array:
[2, 3, 4, 10, 12, 1, 5, 6]
 Compare

...and so on.
Insertion Sort Implementation
Let's see how we can implement insertion sort in Python:
def insertion_sort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] j = i  1 # Move elements of arr[0..i1], that are greater than key, to one position ahead # of their current position while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j = 1 arr[j + 1] = key # Example usage arr = [12, 11, 13, 5, 6] insertion_sort(arr) print("Sorted array is:", arr)
Notice how we use a while
loop to shift elements to the right until we find the correct position for the key
. This ensures that elements are always inserted at their correct positions.
Time Complexity
Understanding the time complexity of insertion sort is crucial. Insertion sort has an average and worstcase time complexity of O(n^2), where n
is the number of elements in the array. This is due to the nested loops: for each element, we potentially compare it with all the previous elements.
However, insertion sort has a bestcase time complexity of O(n), which occurs when the array is already sorted. This makes insertion sort efficient for small datasets or nearly sorted arrays.
Why Use Insertion Sort?
 Simplicity: It's easy to understand and implement.
 Small datasets: It's efficient for small arrays or lists.
 Nearly sorted data: Performs exceptionally well on nearly sorted datasets.
 Inplace sorting: Uses minimal additional memory.
Comparison with Other Sorting Algorithms
Compared to other sorting algorithms like quick sort or merge sort, insertion sort might seem less efficient. However, its simplicity and efficiency with small or nearly sorted datasets make it a valuable tool in a programmer's arsenal.
Hey there! Want to learn more? Cratecode is an online learning platform that lets you forge your own path. Click here to check out a lesson: What Programming Means (psst, it's free!).
FAQ
What is the best case time complexity of insertion sort?
The best case time complexity of insertion sort is O(n), which occurs when the array is already sorted.
Is insertion sort a stable sorting algorithm?
Yes, insertion sort is a stable sorting algorithm, meaning that it preserves the relative order of elements with equal keys.
How does insertion sort handle large datasets?
Insertion sort is not the most efficient for large datasets due to its O(n^2) average and worstcase time complexity. Other algorithms like quick sort or merge sort are more suitable for larger arrays.
Can insertion sort be used for linked lists?
Yes, insertion sort can be adapted for linked lists. It can be more efficient with linked lists because there's no need to shift elements; instead, you simply update pointers.
When should I use insertion sort over other algorithms?
Use insertion sort for small datasets, nearly sorted arrays, or when you need a simple and easytoimplement sorting algorithm. It's also useful when you need a stable sort and have limited additional memory available.