Step 6 of 6
Challenge: quickselect
To find the k-th smallest element (a median, a percentile, "the 95th percentile latency"), you don't need to sort everything. Quickselect partitions like quicksort but only recurses into the side that contains position k, which gives O(n) on average. std::nth_element does exactly this.
Your turn: write int kth_smallest(std::vector<int> v, int k) (k is 0-based; the vector is passed by value so you may rearrange it) using your own partition loop. Pick the middle element as the pivot (swap it to the end first) so already-sorted input stays fast.