# Why isn't selection sort O(n log n)?

We make $n$ insertions and each insertion targets a list of size $k\le n$, so we can make a binary search which takes maximum $\log k\le \log n$. So why isn't the running time of selection sort $O(n \log n)?$

• How can you perform binary search on yet to be sorted array? Order is random, so binary search will not work. – Evil Jun 4 '16 at 0:23
• Try running insertion sort on an array that is nonincreasing (i.e., reverse sorted order). How many operations do you perform? – Ryan Jun 4 '16 at 3:30
• – Raphael Jun 4 '16 at 15:33
• "Why don't things fall up?" I'm not clear on what kind of answer you expect. It doesn't because it doesn't. Perform a proper analysis and you'll see that. – Raphael Jun 4 '16 at 15:34