Insertion Sort
EasyInsertion Sort 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.
Time Complexity
O(n²)Space Complexity
O(1)Category
Sorting
Introduction to Insertion Sort
Insertion Sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
How It Works
The algorithm works similarly to how you might sort playing cards in your hand:
1. Start with the second element (the first element is considered sorted)
2. Compare it with the elements before it
3. Shift elements greater than the key to the right
4. Insert the key in its correct position
5. Repeat for all elements
Algorithm Complexity
Best and Worst Cases
Advantages
1. Simple implementation
2. Efficient for small data sets
3. Adaptive (efficient for data sets that are already substantially sorted)
4. Stable sorting algorithm
5. In-place sorting
6. Online (can sort a list as it receives it)
Disadvantages
1. Inefficient for large lists
2. Performs more writes than Selection Sort
When to Use
Comparison with Selection Sort
Key Takeaways
- Builds sorted array one by one
- Adaptive to sorted data
- Stable sorting algorithm
- In-place sorting
- Efficient for small datasets
Implementation
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
return arr;
}