Steps:
Run the algorithm to see the recorded steps.
Steps:
Run the algorithm to see the recorded steps.
Insertion Sort is a sorting algorithm that builds the sorted portion of the list one element at a time. At each step it removes an element from the unsorted part of the array and inserts it in the correct position inside the already sorted part, shifting the other elements to the right.
Complexity: In the worst and average cases (reverse or random order), the time complexity is O(n²). In the best case (already sorted list), the algorithm only walks through the list once without needing to shift elements, resulting in O(n) time complexity. Like Bubble Sort, it is an in-place algorithm with O(1) space complexity.
1const insertionSort = (arr) => {
2 // Assume the first position is already sorted
3 for (let i = 1; i < arr.length; i++) {
4 let j = i;
5
6 // Keep swapping with the left element while it is smaller
7 while (j > 0 && arr[j - 1] > arr[j]) {
8 [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
9 j--;
10 }
11 }
12 return arr;
13};Insertion Sort is a simple sorting algorithm that builds the sorted list progressively, one element at a time. It works very similarly to the way you would organize playing cards in your hands: you take a new card from the unsorted pile and insert it in the exact position among the cards that are already in order in your hand.
Unlike Bubble Sort, Insertion Sort is very useful in the real world. Although it is inefficient for huge and completely unsorted lists, it is incredibly fast for small lists (fewer than 50 items) or data that is already almost sorted. Because of this surgical efficiency, languages like Python and Java use hybrid algorithms (such as TimSort) that break huge lists into small chunks and trigger Insertion Sort under the hood to sort these fragments at lightning speed.