Selecting the i'th smallest element

Finding the ith smallest element may seem difficult at first. The naive way would be to say, "Hey let's sort it and then we can just pick out the ith one!" We could use MergeSort or even better yet, QuickSort and have it done in O(nlogn). This is called a reduction of our problem: reducing selecting to sorting and then selecting.

It turns out that we can actually accomplish this task by slighting changing QuickSort. Recall that after partitioning, the pivot stays in its "rightful" spot and doesn't get moved in any of recursive calls later on.   So let's say we're looking for the ith element and after the first partition, the pivot is at k.

If k=i, then we know we found the ith element and we're done! If k>i, then recursively partition the left hand side. Otherwise, recursively partition the right side.

What is the running time of this selection algorithm? Well it depends on how good the pivots are. If pivots are chosen in the worst possible way every time, then it will be O(n²). This would be if we chose the smallest or largest element every time, reducing the problem by only one element.

What about the best? This would be the median. Using the master method, we get that this will run in O(n).