There are many parameters that decide whether a sorting algorithm is efficient or not but none of them can satisfy all the criteria at the same time. We generally center around the space and time complexity but there are other parameters as well.
We take operations like swapping, comparisons as constant time taking operations. But computational complexity is also one factor that shouldn't be ignored. Such operations come under this complexity.
Here in the worst case (k=0 or 1), insertion sort will be taking O(n^2) but recall what happens in insertion sort :
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
We shift the elements towards right in order to sort (arr[j+1]=arr[j]). This isn't called swapping. It may be termed as "movements".
In other sorting algo, we swap 2 elements where we need to do assignments for 3 times to swap using temporary variables during each iteration.
Whereas here only 1 time assignment is done per iteration.
In average case when the array is nearly sorted, the no. of movements vs no. of swappings make a significant difference.
Though asymptotic time complexity doesn't vary but computational complexity does.
I summarized the knowledge I had on it. Open to suggestions and additions :)
