(NOTE: I am dividing the array into sub-arrays containing 5 elements in my example)
I understand that the median-of-medians algorithms splits the n-input array into floor(n/5) groups with an additional group-containing (n)mod5 elements and then finds the median element of each sorted group (the 3rd element in groups with 5 elements) and so on.
My question is if one of the groups had 2 or 4 elements, which element would be chosen as the median of that group (assuming that the group has already been sorted).
For a group with 2 elements, the immediate left-most value in the sorted group will be chosen.
e.g. for a group of
[2,5]
2 will be chosen as the median of the group.
For a group of 4 elements, the 2nd element will be the median.
To generalise this, the median in a group with an even number of elements will be the left median (according to most examples in books and online). However, it is perfectly fine to choose the right median in an even list as long as this strategy is used consistently throughout the algorithm.