Loading...
A simple and efficient algorithm for small datasets. It builds the sorted array one element at a time by repeatedly taking an element and inserting it into its correct position.
function insertionSort(arr) {
// Start with second element (index 1)
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
let j = i - 1;
// Move elements greater than key one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// Insert key at correct position
arr[j + 1] = key;
}
return arr;
}
// Time Complexity:
// Best case: O(n) - already sorted
// Average case: O(n²)
// Worst case: O(n²) - reverse sorted
// Space Complexity: O(1) - in-placefunction binaryInsertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
// Use binary search to find insertion position
let left = 0;
let right = i;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] > key) {
right = mid;
} else {
left = mid + 1;
}
}
// Shift elements and insert
for (let j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = key;
}
return arr;
}
// Reduces comparisons to O(n log n)
// But shifts are still O(n²) in worst casefunction insertionSortRecursive(arr, n = arr.length) {
// Base case
if (n <= 1) return arr;
// Sort first n-1 elements
insertionSortRecursive(arr, n - 1);
// Insert the nth element at correct position
const last = arr[n - 1];
let j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
return arr;
}
// Same time complexity but uses recursion
// Space: O(n) due to recursive callsArray is already sorted. Each element requires only one comparison.
Random order. On average, each element needs to be compared with half the sorted elements.
Array is reverse sorted. Each element must be compared with all previous elements.