codaBack to Academy
sorting
Insertion Sort
Insertion Sort builds the sorted array one element at a time by repeatedly picking the next unsorted element and inserting it into its correct position among the previously sorted elements. It is highly efficient for small or nearly sorted datasets and serves as the basis for more advanced algorithms like Shell Sort.
Use Cases
- •Small datasets where overhead of complex algorithms is not justified
- •Nearly sorted arrays where few elements are out of place
- •Online sorting where elements arrive one at a time
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n) | O(n²) | O(n²) |
| Space | O(1) | ||
Visualization
64
34
25
12
22
11
90
Implementation
Output
Click "Run Code" to see output...