Sorting an array to answer a question about it is often the wrong move, and this post is about the two ways to notice. The first: sometimes you do not need the array sorted, only partly sorted. Quicksort’s partition step puts one element in its final place and separates everything else into two sides — and if all you want is the k-th largest, that single step is enough, and repeating it is O(n) rather than O(n log n). Four problems below are that idea. The second: sometimes you do want it sorted, and then sorted order pays you back READ MORE