python sort complexity
nlog2n.
As others have mentioned, the built-in sorting algorithm of Python uses a special version of merge sort, called Timsort, which runs in nlog2n time.
That’s pretty good; we generally can’t get much better than nlog2n (with the exception of sorts which are slightly optimized for certain arrangements of data).
You can read more about how Timsort works (it’s pretty cool!) here: