1. No matter what, insertion sort ALWAYS does the same thing. So, even if the data is basically sorted already, it still will do the same amount of work. 2. In a single pass of the data you can find the two elements that are out of place by looking for an element where: some_list[i] > some_list[i+1] Since it's just a single pass through the data, the runtime would be O(n), linear.