This video from the Tim Sort series focuses on making the intermediate merge operations efficient. The Tim Sort algorithm performance is heavily dependent on merging sorted arrays efficiently.
A merge operation uses auxiliary memory equal to the size of the smaller chunk/run. This is an improvement over the standard Merge Sort approach which constructs the sorted array outside the other two arrays being merged.
Another optimisation in the algorithm is using a program stack instead of the system stack. This avoids recursive calls and allows us to choose which two runs to merge.
The final improvement is to optimise the sizes of the merging arrays. This is done by using invariants in the stack, making the stack sorted in ascending order of lengths downwards.
The final video will be on using some artificial intelligence to merge runs even more efficiently!
References:
Java: http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java
Article: https://bugs.python.org/file4451/timsort.txt
Social links:
Facebook: https://facebook.com/gkcs0/
Quora: https://www.quora.com/profile/Gaurav-Sen-6
LinkedIn: https://www.linkedin.com/in/gaurav-sen-56b6a941/
