Quickly determine if insertion sort or quick sort is better

Question

I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost sorted, use insertion sort if it is, or quicksort otherwise. I've been searching this up all day but no luck.

The alternative solution is to shuffle the array and use quicksort every time, but this passes up on the opportunity to do 30% of the sorts faster.

The way I thought of is to compare consecutive terms, find the number of consecutive pairs out of order, and use that to estimate the entire array, but its not very reliable.

This seems like a common problem, so I was wondering what the "official" solution(s) is.

Answer 1

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).