On Quickselect, partial sorting and Multiple Quickselect

We present explicit solutions of a class of recurrences related to the Quickselect algorithm. Thus we are immediately able to solve recurrences arising at the partial sorting problem, which are contained in this class. Furthermore we show how the partial sorting problem is connected to the Multiple Quickselect algorithm and present a method for the calculation of solutions for a class of recurrences related to the Multiple Quickselect algorithm. Further an analysis of an algorithm for sorting a subarray A[r…r+p−1], given the array A[1…n], is provided.