Worst-case input for median-of-medians with groups of size 3
Whether or not the median-of-medians algorithm with groups of size 3 runs in linear time is an open problem as said in [1] (while they proposed a variant running in linear time). I checked some follow-up papers and no one has a progress on showing the complexity of this algorithm. I believe it still remains open now.



[1] Chen, K., &amp; Dumitrescu, A. (2015, August). Select with groups of 3 or 4. In Workshop on Algorithms and Data Structures (pp. 189-199). Springer, Cham.