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.

  • $\begingroup$ 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. $\endgroup$ – Kyle Jones Mar 26 at 3:16
  • $\begingroup$ but that is probably slower than just using quicksort for everything $\endgroup$ – Will Kanga Mar 26 at 3:25
  • $\begingroup$ Maybe, maybe not. As with all heuristics, test. $\endgroup$ – Kyle Jones Mar 26 at 3:26
  • $\begingroup$ 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. $\endgroup$ – greybeard Mar 26 at 7:12
  • $\begingroup$ Do you understand why the two different cases arise? $\endgroup$ – Joffan Mar 26 at 12:01

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.