CSC148H1 Lecture Notes - Lecture 11: Timsort, Mersenne Prime, Sorting Algorithm
1
CSC148H1 Full Course Notes
Verified Note
1 document
Document Summary
This describes an adaptive, stable, natural mergesort, modestly called timsort (hey, i earned it ). It has supernatural performance on many kinds of partially ordered arrays (less than lg(n!) comparisons needed, and as few as n-1), yet as fast as python"s previous highly tuned samplesort hybrid on random arrays. In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs intelligently. Everything else is complication for speed, and some hard-won measure of memory efficiency. + timsort can require a temp array containing as many as n//2 pointers, which means as many as 2*n extra bytes on 32-bit boxes. It can be expected to require a temp array this large when sorting random data; on data with significant structure, it may get away without using any extra heap memory.
