Tim Sort
Tim Sort Animation
Tim Sort Infographic
Methodology
Tim Sort is a hybrid approach that combines Binary Insertion Sort and Merge Sort. And it's strength is that it takes advantage of any naturally occurring ordering in the data. Below are the specific steps.
(1) Create Runs
Create runs based on trends of increasing and decreasing numbers
Determine run trend using the first two unique numbers
When an observed number disagrees with preexisting trend:
if
current run length < min run size:Then Binary Insert number into run
else:
Run is completed. Add run to runs array.
Note, once a run is completed, if it’s a
decreasing trend, then reverse it
observed number becomes first number
of a new trend
(2) Merge Runs
(A) Pop last two runs off runs array and merge them together
use non-galloping merge process first
use galloping merge process when either of the following occurs:
[While doing the non-galloping merge]
number of consecutive selections from an array > min gallop size.
[While already doing galloping merge]
chunk galloped > min galloped size
after each gallop, if chunk galloped <= min galloped size
decrement min galloped size
otherwise increment min galloped size
(B) Append merged result back onto runs array
once there is only one run remaining,
merging process is complete
Things to Consider
In some implementations of Tim Sort, the min galloped size is either:
(A) calculated by a formula which depends of N
(B) is an arbitrarily number selected by developer
Complexity
Time Complexity: N log(N)
Space Complexity: N
Stable
