is there a "partial sorting" algorithm that is more efficient than a full sort that will yield those three groups?
Since you're talking about "real-life" scenarios rather than theoretical asymptotics, here's something you could do:
* Take a number of uniformly and independently sampled values from the array, and use them to estimate the distribution of values; or at least - estimate the values of your first and third quartiles. The exact number of samples depends on the probability-and-accuracy combination you're interested in, and what you know about the size of the value space; but let's not go into the statistical details here. Suffice it to say that getting a value in a given quarter happens with probability 1/4, independently of other samples, so you can apply large deviation bounds.
* Now that you have a likely-decent-estimate of the quartiles, perform your filtering. With very high probability, you now have a little more or a little less than 50% of the elements, ranging between around the 1st quartile and around the 3rd quartile.
* You can know how far you are from having gotten the actual quartiles, by keeping count of how many elements are in each of the 3 sets you've formed.
This is usually enough for your real-life needs, as the choice of quartiles is typically arbitrary, i.e. you usually want "the stuff that's around the middle", and the above gives you this. 964
The overall time complexity will be linear in the length of the array.
... Now, you might be asking - why did I even bother suggesting this solution? You already got suggestions of linear-time solutions (even if it's estimated-linear-time), right?
Well, the answer is this is efficient in real life. Your $O(\cdot)$ constant will be extremely low in term of abstract computational operations; and your memory access pattern (after the initial sampling) will be ideal: A clean single consecutive pass over your elements. Cache friendly, CPU prefetch friendly, and it can even be parallelized relatively well.
Are there additional savings if the array is always a power of 2 (assume N >= 4)?
I doubt it. You're thinking like a theoretician here - they/we always hate it when we have to soil our neat pseudo-code with some "if it's not divisible by two" corner cases. 603