Timsort is an O(n log n) sorting algorithm built for the real world and not academia. Timsort is the default sorting algorithm in Python, Java, and Android. 🤖
If the size of the array is less than 64, Timsort just runs insertion sort.
If the size is more than 64, Timsort tries to find "natural runs" in the array.
In the real world, many lists have "natural runs" in them. These are sections of the list which are strictly ascending. An example of this is "1, 2, 3" in this list:
[5, 4, 1, 2, 3, 6, 7]
If it finds a section which is strictly descending like [3, 2, 1] it'll flip them into ascending - [1, 2, 3].
Timsort will then perform merge sort on these natural runs, and some other things such as entering galloping mode. If you want to learn more about Timsort, go to timsort.skerritt.tech
If you want more like this, follow @brandon.codes
or join my weekly newsletter at email.skerritt.tech 🔥🔥
PS: I'm starting a new series on my Instagram. Super mini blog-posts. Some will be based on articles I've written, some will not. Please do let me know what you think, it took me a lot longer than I expected to set this up! ✨✨