A simple sorting algorithm that builds the final sorted array one item at a time, much like how you might sort playing cards in your hands.
Parameters
12
Visualization
Step: 0
Click Randomize or Step to begin sorting.
Algorithm Insight
Insertion Sort maintains a sorted sub-list and inserts new elements into their correct position.
1.Assume the first element is already sorted.
2.Pick the next element as the Key.
3.Shift sorted elements that are greater than the Key to the right.
4.Insert the Key into its correct slot.
Complexity
Average CaseO(N²)
Space ComplexityO(1)
Deconstructing Insertion Sort
The intuitive algorithm that sorts data the same way you'd sort a hand of playing cards.
Quick Context: What is Insertion Sort?
Insertion Sort is a simple, intuitive sorting algorithm that builds a final sorted array one element at a time. It works by taking an element from the unsorted part and "inserting" it into its correct position in the already sorted part. Imagine you're picking up playing cards one by one and arranging them in your hand—you'd pick up a card and slide it into the right spot among the ones you're already holding. That's Insertion Sort in a nutshell.
The Core Idea: The Sorted Sub-array
The algorithm divides the array into two conceptual parts: a sorted sub-array at the beginning and an unsorted sub-array at the end. Initially, the sorted sub-array contains only the first element.
Pick a Key: The algorithm iterates from the second element to the end. The current element being considered is the "key".
Compare and Shift: The key is compared with the elements in the sorted sub-array, moving from right to left.
Shift Greater Elements: If an element in the sorted sub-array is greater than the key, it's shifted one position to the right to make space.
Insert the Key: This shifting continues until we find an element that is smaller than or equal to the key, or we reach the beginning of the array. The key is then inserted into the newly created empty slot.
Guided Experiments with the Visualizer
Initial State: Click "Randomize Array". You'll see a set of bars of varying heights. The first element is considered the initial "sorted" part.
First Step: Click "Next Step". The second element is selected as the "key" (highlighted in yellow). It's compared with the first element. If the key is smaller, they swap. The first two elements now form the sorted sub-array.
Observe the Shifting: Click "Next Step" again. The third element becomes the new key. Watch as it's compared with the elements in the sorted part (to its left). You'll see larger elements shift to the right one by one, creating a space for the key to be inserted. The "Feedback Box" will describe each comparison and shift.
Auto-Run: Click "Auto-Run" to see the entire process unfold. The sorted sub-array (light green) grows from left to right as each key is picked from the unsorted part and placed into its correct position.
Best and Worst Cases:
Best Case: After sorting, click "Auto-Run" again on the already sorted array. Notice that the algorithm just zips through, as no elements need to be shifted. This is O(n).
Worst Case: Create a reverse-sorted array (or use the "Reverse" button if available). Now, run the algorithm. Every single element has to be shifted the maximum number of times. This demonstrates the O(n²) complexity.
Performance and Use Cases
Time Complexity:
Worst and Average Case: O(n²) — Occurs when the array is reverse-sorted. Not efficient for large, random arrays.
Best Case: O(n) — Occurs when the array is already sorted.
Space Complexity: O(1) — It's an "in-place" algorithm, meaning it requires no extra memory.
When to Use It: Insertion Sort is highly efficient for small datasets and for datasets that are already partially sorted. Because of this, it's often used as a component in more complex hybrid sorting algorithms (like Timsort, Python's default).
Key Takeaways
Simple and Intuitive: Easy to understand and implement.
In-Place: Sorts the array without needing extra storage.
Adaptive: Performance improves as the array becomes more sorted.
Stable: It does not change the relative order of elements with equal values.
Best for Small or Nearly Sorted Data: Its O(n²) complexity makes it unsuitable for large, unsorted lists.
Cheat sheet
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds a final sorted array one element at a time. It works by taking an element from the unsorted part and "inserting" it into its correct position in the already sorted part. Imagine you're picking up playing cards one by one and arranging them in your hand—you'd pick up a card and slide it into the right spot among the ones you're already holding. That's Insertion Sort in a nutshell.