And this all is good but TimSort allocates O(N) memory. The constant in front of N is smallish less then 1.0 but it could cause some grief.
Worst case is O(n/2), but it starts small and doubles in size as needed. On a partially sorted array, it may only use a small amount of memory.
