If I’m not mistaken, quick sort is worst case O(n^2), merge sort is what actually achieves O(nlogn), the point is that quicksort is on average more memory (and time?) efficient
When using a random pivot, the worst case becomes exponentially more unlikely the larger the n. The O notation only cares about the complexity when n approaches infinity. So when n approaches infinity, the likelihood of O(n^2) performance approaches 0 (and the likelihood of O(n log n) approaches 1).
If I’m not mistaken, quick sort is worst case O(n^2), merge sort is what actually achieves O(nlogn), the point is that quicksort is on average more memory (and time?) efficient
Maybe.
When using a random pivot, the worst case becomes exponentially more unlikely the larger the n. The O notation only cares about the complexity when n approaches infinity. So when n approaches infinity, the likelihood of O(n^2) performance approaches 0 (and the likelihood of O(n log n) approaches 1).
I think it’s fine to call it O(n log n).
That’s when you add a w.h.p. (with high probability)