Kth smallest element in an arra What would be an efficient method to find the kth smallest element in an array with worst case time complexity being $ O(n) $?
You can use quickselect with median of medians to find a good pivot so that the total running time is linear in the worst case.