void insertionSort(vector<int> &arr, int n) {
for(int i = 1 ; i<=n-1 ; i++){
int j=i;
while(j>0 && arr[j]<arr[j-1]){
swap(arr[j], arr[j-1]);
j--;
}
}
}
| Type | Complexity | Explanation |
|---|---|---|
| Time (Best) | O(n) |
Already sorted array, only 1 comparison per element |
| Time (Average) | O(n²) |
Each element compared to about half of the sorted portion |
| Time (Worst) | O(n²) |
Reverse sorted array, each element compared to all before it |
| Space | O(1) |
In-place sorting, no extra data structures used |
| Stable? | Yes | Equal elements are not swapped (but your swap() version is not stable unless modified) |
| Used in | Small data sets, mostly sorted arrays, online sorting (real-time input processing) |