# Quickly determine if insertion sort or quick sort is better

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.

• I doubt that there's any standard; there usually isn't for heuristics like what you're describing. What I would do is run insertion sort with some ad-hoc instrumentation inside it that tracks how much data is being moved during the sort. If it becomes clear that insertion sort is moving too much data for the array to be almost sorted, stop and call quicksort. Mar 26, 2021 at 3:16
• but that is probably slower than just using quicksort for everything Mar 26, 2021 at 3:25
• Maybe, maybe not. As with all heuristics, test. Mar 26, 2021 at 3:26
• I've been searching this up all day but no luck That does not seem an advisable approach, neither to problem solving nor to presenting a(negative) result. Detecting and exploiting runs has been done in natural merge sort and timsort. Mar 26, 2021 at 7:12
• Do you understand why the two different cases arise? Mar 26, 2021 at 12:01

## 1 Answer

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