Quickly determine if insertion sort or quick sort is better
Quicksort is better unless the number of items in the wrong place is O(log n) only. There is a simple sorting algorithm that runs in O (n) if the number of items in the wrong place is a bit less than O (n / log n): Scan the array, and whenever two items are out of order put them into a separate array. Sort the separate array with Quicksort, then merge both arrays.
This will be not O(n), but faster than Quicksort, if the number of items in the wrong place is much lower than n, say O (n / sqrt(log(n)). The scanning + merging is obviously O(n). If t items are in the wrong order, then sorting them using Quicksort takes O (t log t), so it's O(n) in total if (t log t) = O(n), and asymptotically faster than Quicksort if t = o(n).