Your Progress
17/30 completed
57% complete. Continue learning to master DSA!
Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time, similar to how people sort playing cards in their hands.
Key Takeaways
- Insertion sort is adaptive, efficient for small data sets, and often used as part of more sophisticated algorithms
- Time complexity: O(n²) worst and average case, O(n) best case (when array is already sorted)
- Space complexity: O(1) as it sorts in-place
- It's a stable sorting algorithm that preserves the relative order of equal elements
- Works well for arrays that are already substantially sorted
How Insertion Sort Works
Insertion sort works by building a sorted array one element at a time. It takes one element from the input data in each iteration and finds its correct position within the sorted part by comparing with each element.
Algorithm Steps
- Start with the second element (assume the first element is already sorted)
- Compare the current element with the previous elements
- If the previous element is greater than the current element, move the previous element one position ahead
- Repeat step 3 until you find the correct position for the current element
- Place the current element in its correct position
- Repeat steps 2-5 for all elements in the array
Visual Example
Let's sort the array [12, 11, 13, 5, 6] using insertion sort:
Initial array: [12, 11, 13, 5, 6] Pass 1: - Consider 11 - 12 > 11, so move 12 ahead: [12, 12, 13, 5, 6] - Place 11 in correct position: [11, 12, 13, 5, 6] Pass 2: - Consider 13 - 13 > 12, already in correct position: [11, 12, 13, 5, 6] Pass 3: - Consider 5 - 13 > 5, so move 13 ahead: [11, 12, 13, 13, 6] - 12 > 5, so move 12 ahead: [11, 12, 12, 13, 6] - 11 > 5, so move 11 ahead: [11, 11, 12, 13, 6] - Place 5 in correct position: [5, 11, 12, 13, 6] Pass 4: - Consider 6 - 13 > 6, so move 13 ahead: [5, 11, 12, 13, 13] - 12 > 6, so move 12 ahead: [5, 11, 12, 12, 13] - 11 > 6, so move 11 ahead: [5, 11, 11, 12, 13] - 5 < 6, so 6 is in correct position: [5, 6, 11, 12, 13] Final sorted array: [5, 6, 11, 12, 13]
Implementing Insertion Sort
JavaScript Implementation
function insertionSort(arr) {
const n = arr.length;
// Start from the second element
for (let i = 1; i < n; i++) {
// Store the current element
let current = arr[i];
// Find the correct position for the current element
let j = i - 1;
while (j >= 0 && arr[j] > current) {
// Move elements greater than current one position ahead
arr[j + 1] = arr[j];
j--;
}
// Place current element in its correct position
arr[j + 1] = current;
}
return arr;
}
// Example usage
const array = [12, 11, 13, 5, 6];
console.log(insertionSort(array)); // Output: [5, 6, 11, 12, 13]Python Implementation
def insertion_sort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
# Store the current element
current = arr[i]
# Find the correct position for the current element
j = i - 1
while j >= 0 and arr[j] > current:
# Move elements greater than current one position ahead
arr[j + 1] = arr[j]
j -= 1
# Place current element in its correct position
arr[j + 1] = current
return arr
# Example usage
array = [12, 11, 13, 5, 6]
print(insertion_sort(array)) # Output: [5, 6, 11, 12, 13]C++ Implementation
#include <iostream>
#include <vector>
std::vector<int> insertionSort(std::vector<int> arr) {
int n = arr.size();
// Start from the second element
for (int i = 1; i < n; i++) {
// Store the current element
int current = arr[i];
// Find the correct position for the current element
int j = i - 1;
while (j >= 0 && arr[j] > current) {
// Move elements greater than current one position ahead
arr[j + 1] = arr[j];
j--;
}
// Place current element in its correct position
arr[j + 1] = current;
}
return arr;
}
int main() {
std::vector<int> array = {12, 11, 13, 5, 6};
std::vector<int> sorted = insertionSort(array);
// Print the sorted array
for (int num : sorted) {
std::cout << num << " ";
}
// Output: 5 6 11 12 13
return 0;
}Time and Space Complexity
Time Complexity
- Best Case: O(n) - When the array is already sorted
- Average Case: O(n²) - When elements are in random order
- Worst Case: O(n²) - When the array is sorted in reverse order
The time complexity depends on the input array configuration. Insertion sort performs well with small data sets or when the array is nearly sorted.
Space Complexity
- Space Complexity: O(1) - Insertion sort is an in-place sorting algorithm
- It only requires a single additional memory space for the temporary variable (current)
Advantages and Disadvantages
Advantages
- Simple implementation: Easy to understand and code
- Adaptive: Efficient for datasets that are already substantially sorted
- Stable: Preserves the relative order of equal elements
- In-place: Requires only O(1) extra space
- Online: Can sort a list as it receives it
- Efficient for small datasets: Low overhead makes it fast for small arrays
Disadvantages
- Inefficient for large datasets: O(n²) time complexity makes it impractical for large arrays
- Not suitable for reversed data: Performs poorly when elements are in reverse order
- Requires shifting of elements: Each insertion may require many element shifts
- Outperformed by more advanced algorithms: Merge sort, quick sort, and heap sort are more efficient for large datasets
Comparison with Other Sorting Algorithms
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
Compared to other sorting algorithms, insertion sort has the following characteristics:
- More efficient than selection sort for partially sorted arrays
- Similar to bubble sort but generally performs fewer comparisons
- Less complex than merge sort and quick sort, but less efficient for large datasets
- One of the few quadratic-time algorithms that is stable without requiring extra space
- Used in practice for small arrays or as part of more complex algorithms like Shell sort
Practical Applications
When to Use Insertion Sort
- Small datasets: When the array size is small (typically less than 20 elements)
- Nearly sorted data: When most elements are already in the correct position
- Online sorting: When you need to sort data as it arrives (insertion sort can process one element at a time)
- Auxiliary algorithms: As part of more complex algorithms like Shell sort or QuickSort (for small partitions)
- Limited memory environments: When memory usage needs to be minimized
Real-World Scenarios
- Card sorting: Mimics how people sort playing cards in their hands
- Real-time data processing: For continuously arriving data that needs to be maintained in sorted order
- Library book sorting: When librarians place new books in the correct position on a shelf
- Embedded systems: Where resources are limited and data sets are small
- Hybrid sorting algorithms: TimSort (used in Python and Java) uses insertion sort for small subarrays
Optimization: Binary Insertion Sort
Binary insertion sort is an optimization of insertion sort that uses binary search to find the correct position for inserting elements, reducing the number of comparisons.
Implementation
function binarySearch(arr, target, start, end) {
if (start > end) return start;
const mid = Math.floor((start + end) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] > target) {
return binarySearch(arr, target, start, mid - 1);
} else {
return binarySearch(arr, target, mid + 1, end);
}
}
function binaryInsertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
const current = arr[i];
const j = i - 1;
// Find location where current should be inserted using binary search
const location = binarySearch(arr, current, 0, j);
// Move all elements after location one position ahead
for (let k = j; k >= location; k--) {
arr[k + 1] = arr[k];
}
// Place current at its correct location
arr[location] = current;
}
return arr;
}Binary insertion sort reduces the number of comparisons to O(n log n), but the number of shifts remains O(n²) in the worst case. It's beneficial when comparison operations are significantly more expensive than shift operations.
Conclusion
Insertion sort is a simple, efficient, and adaptive sorting algorithm that works well for small datasets and partially sorted arrays. While it's not suitable for large datasets due to its quadratic time complexity, its simplicity, stability, and small constant factors make it valuable in certain scenarios.
Key Points to Remember
- Insertion sort is efficient for small datasets and nearly sorted arrays
- It's an adaptive algorithm that performs better as the input array becomes more sorted
- As a stable, in-place algorithm, it preserves relative order and uses minimal extra space
- Binary insertion sort can reduce comparisons, but not shifts
- For large datasets, consider using more advanced algorithms like merge sort or quick sort
Next Steps
To continue your learning about sorting algorithms, explore these related topics:
Related Tutorials
Related Tutorials
Selection Sort
Compare with another elementary sorting algorithm.
Learn moreBubble Sort
Another simple sorting algorithm with similar complexity.
Learn moreMerge Sort
A more efficient divide-and-conquer sorting algorithm.
Learn more