This is awesome, thanks for the detailed explanation with the math! It gives a great view why we can never do better than Ω(nlogn) when it comes to comparison sorting.
thanks & thanks for watching! (aside: we can't do better than Ω(n*log(n) rather than O(n*log(n), big O is an upperbound so it guides on bounding from above, we want to bound from below since we are looking for the best we can do. You can upperbound in the best, average, & worst case. You can lowerbound in the best, average, & worse case. Lower-bounding the best you can do makes the most sense in this discussion.)
the thing i don't hear from anyone is that any comparison sorts can be reduced to two operations: binary search in new (initially empty) sorted array (search for appropriate index of another variable in there), and insertion at that index. First is O(logn) (for much more obvious reasons than all of this), second-O(n). And since the logic is that you need exactly n insertions and one binary search before every insertion, overall complexity will be just a multiplication of these. Which results in O(nlogn).
