Insertion Sort on a Partially Sorted List
When you have a partially sorted list, you can change the definition of the Priority Queue you use in Insertion Sort so that the new elements are first added to the end of the queue. This way, the algorithm’s time complexity changes to $O(n+I)$ where $I$ is the number of inversions1 in a list.
A pair of elements in the list that start out in the wong relative order. ↩︎