I'm trying to figure out how to calculate the sample size I need to ensure a certain confidence that the rank of the sample median is within a certain interval around the true median position. Digging through Wikipedia only yielded info about confidence in (real) median values, which are completely irrelevant to my application.

Background: I'm playing around with a randomized incremental QuickSort algorithm. I want to choose pivots near the median to avoid expensive "bad" partitions for long lists, but I don't want to waste time taking excessively large samples.