Imagine a sorted deck of N cards that has been cut K times by moving X cards from the top to the bottom (X is a different / random amount each time, X is always < N) – what would be the best way to sort this, knowing that there are “chunks” of sorted cards?
I am thinking something along the lines of going 1 by 1 until reaching one that is out of order, and then splitting what I reached out as a “chunk”, and then continuing until I have (K+1?) chunks, and then sorting the chunks via a standard sort, however I am not sure if this is the best solution, nor exactly how to describe its complexity in terms of big-o
(for the big-o, I think it would be N (chunking) + (k+1)log(k+1) for the sorting -> k+1(log(k+1)), but I am not sure)
Timsort, which combines Merge and Insertion sort to do exactly what you describe. It makes use of already sorted parts of the collection to speed sorting.
Effectively it’s a merge sort up till it finds enough “chunks” to use insertion sort. This gives it a worst case and average case time complexity of O(nlogn), same as the base merge sort. It gains the O(n) best case of insertion sort.
It is the default sort for Python as well as an increasing number of other platforms.
0