Insertion Sort: A Step-by-Step Approach
Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: it is simple to implement, efficient for small data sets, and efficient for data sets that are already substantially sorted.
How Insertion Sort Works
The algorithm iterates through the input array and for each element, it finds the correct position within the already sorted portion of the array and inserts it there. This process is repeated until the entire array is sorted.
Insertion sort divides the array into a sorted and an unsorted region.
It picks an element from the unsorted region and inserts it into its correct position in the sorted region.
Imagine you have a hand of playing cards. You pick up cards one by one and insert them into their correct position in your hand so that your hand remains sorted. This is precisely how insertion sort operates. It starts with the second element (index 1) and compares it with the element before it (index 0). If the second element is smaller, it's swapped. Then, it moves to the third element and compares it with the elements in the sorted portion (elements at index 0 and 1) until it finds its correct place. This continues for all elements.
It is efficient for small data sets.
Illustrative Example
Let's consider an unsorted array:
[12, 11, 13, 5, 6]
Step 1: Consider the first element 12 as sorted. Array: [12, 11, 13, 5, 6]. Sorted: [12]. Unsorted: [11, 13, 5, 6].
Step 2: Pick 11. Compare with 12. Since 11 < 12, swap them. Array: [11, 12, 13, 5, 6]. Sorted: [11, 12]. Unsorted: [13, 5, 6].
Step 3: Pick 13. Compare with 12. 13 > 12, so 13 is in its correct place. Array: [11, 12, 13, 5, 6]. Sorted: [11, 12, 13]. Unsorted: [5, 6].
Step 4: Pick 5. Compare with 13. 5 < 13, shift 13 right. Compare with 12. 5 < 12, shift 12 right. Compare with 11. 5 < 11, shift 11 right. Insert 5 at the beginning. Array: [5, 11, 12, 13, 6]. Sorted: [5, 11, 12, 13]. Unsorted: [6].
Step 5: Pick 6. Compare with 13. 6 < 13, shift 13 right. Compare with 12. 6 < 12, shift 12 right. Compare with 11. 6 < 11, shift 11 right. Compare with 5. 6 > 5, insert 6 after 5. Array: [5, 6, 11, 12, 13]. Sorted: [5, 6, 11, 12, 13]. Unsorted: [].
Final sorted array: [5, 6, 11, 12, 13].
Text-based content
Library pages focus on text content
It is inserted at the beginning of the sorted subarray.
Time and Space Complexity
| Scenario | Time Complexity |
|---|---|
| Best Case (Already Sorted) | O(n) |
| Average Case | O(n^2) |
| Worst Case (Reverse Sorted) | O(n^2) |
The space complexity for Insertion Sort is O(1) because it sorts the array in-place, meaning it does not require any additional auxiliary space proportional to the input size.
Insertion Sort is an 'in-place' sorting algorithm, meaning it sorts the array without needing extra memory.
When to Use Insertion Sort
Insertion sort is a good choice for:
- Small datasets.
- Datasets that are already partially sorted.
- Situations where simplicity of implementation is prioritized over raw speed for large datasets.
- As a component of more advanced sorting algorithms like Timsort (used in Python) and Introsort.
O(1)
Learning Resources
A comprehensive explanation of the Insertion Sort algorithm with C++, Java, and Python implementations and detailed complexity analysis.
Provides a clear, step-by-step walkthrough of Insertion Sort, including its logic, pseudocode, and time complexity.
An interactive visualization that demonstrates how Insertion Sort works on different datasets, aiding in conceptual understanding.
A beginner-friendly explanation of Insertion Sort, covering its algorithm, pseudocode, and complexity with examples.
The Wikipedia page offers a detailed overview of Insertion Sort, its history, variations, and comparisons with other sorting algorithms.
This course covers fundamental algorithms, including sorting, with in-depth theoretical explanations and practical implementations.
Khan Academy provides a clear and concise video explanation of the Insertion Sort algorithm, suitable for beginners.
The foundational textbook for algorithms, offering a rigorous treatment of sorting algorithms, including Insertion Sort.
A practical guide to understanding and implementing Insertion Sort, with interactive code examples.
Udemy offers various courses that delve into data structures and algorithms, often featuring detailed modules on sorting algorithms like Insertion Sort.