I think there is a mistake in the solution. The mutual recursion should be between median_of_medians and find_Kth_smallest_number_rec, rather than between median_of_medians and partition.

• Having a mutual recursion between median_of_medians and partition: say we are at the end of median_of_medians and we have a medians list/array with 3 medians (let's say [95, 4, 5], and we call partition on this array. partition will call median_of_medians on this array, which will hit the first if statement inside median_of_medians and return the first median of the 3 medians (i.e.95). We are back in partition again and will try to find the pivot and do some sorting. This will sort the medians list/array into [4, 5, 95] and return the index of 95 which is equal to 2 inside this array (in reality it's more like p + 2 where p comes from the earlier recusive calls). We go up a level again to the median_of_medians that called partition and return straight away the index 2. Then we are at partition again and this time 'median' = 2 which doesn't make sense as median should be a value not an index. But even if it were 95 (i.e. the value), it still would not make sense as 95 is not a median of the original medians array/list.

• Having a mutual recursion between median_of_medians and f_Kth_smallest_number_rec: say we are at the end of median_of_medians and we have a medians list/array with 3 medians like above ([95,4,5]), and we call find_Kth_smallest_number_rec on this array with k=1 (the index of the median in a size 3 array is 1). When the find_Kth_smallest_number_rec function finishes, we know we will have the number that is at the Kth index (i.e. index 1) of the medians array which is 5. This is the actual median that we want out of the medians array!

References: https://stackoverflow.com/questions/52461306/something-i-dont-understand-about-median-of-medians-algorithm

https://stackoverflow.com/questions/9489061/understanding-median-of-medians-algorithm