There are a couple of algorithms which are useful for this particular problem. Although they are usually described as selection algorithms, which compute the $k^{th}$ order statistic of an unordered dataset, they can also be used for in-place partitioning of the data-set; a $V_1, V_2, ..., V_n$ is partitioned at $k$ if $\forall i<k,V_i\le V_k$ and $\forall i>k,V_i\ge V_k$.
In other words, $V_k$ is at the position it would be if $V$ were fully sorted, and no preceding element is greater. This is sometimes called an "unordered partial sort", but I think "partition" describes it better.
Unlike sorting, this operation can be performed in time $O(n)$ and space $O(1)$, although the most common algorithm only promises expected $O(n)$ time. (In theory, worst-case $O(n^2)$ is possible, but superlinear times are rare with random data and the guaranteed $O(n)$ time algorithm has a lot of overhead.) The best-known instance of such an algorithm is C.A.R. Hoare's Quickselect but there are many other possibilities.
For computing a truncated subsequence, such as the interquartile range, you can gain a bit of extra efficiency by doing both partitions at the same time. Of course, this doesn't improve the asymptotic efficiency, but the real-world execution time is less.
Quickselect can be thought of as the beginning of a quicksort (and it's not a coincidence that Hoare also developed the quicksort algorithm.) It avoids the $\log n$ factor by only recursing on one side of the pivot. (Or, equivalently, looping, which demonstrates $O(1)$ space.) Since the only outcome required is that the vector be partitioned at $V_k$, it's only necessary to process one side of the selected pivot. This should be reasonably intuitive; after partitioning with the pivot, all the elements preceding the pivot point are no greater than the pivot, and all elements following it are at least as great. There must either be at least $k-1$ preceding elements or at least $n-k$ following elements (or both); whichever side of the array satisfies that condition cannot possibly contain the $k^{th}$ order statistic, and thus there is no need to examine it further.
As with quicksort, selecting a good pivot --or at least, not selecting a bad pivot-- is crucial. If you somehow managed to always select a pivot whose value is near the minimum or maximum of the dataset, you'd end up with quadratic time. (But since all recursive calls are tail calls, even in pathological cases, the space requirement continues to be constant.) In practice, you can avoid this problem by selecting a random pivot and using a partitioning algorithm which is tolerant of datasets with large numbers of repeated values.
To compute the interquartile range, you might start by using the selection algorithm to find $V_{n/4}$ and then call the algorithm again on the upper three-quarters of $V$ to find $V_{3n/4}$. But it's evident that this involves quite a bit of duplication of work at the beginning. A better solution is to partition the array until a pivot is discovered which is inside the interquartile range. Once the array is partitioned at that point, quickselect can be called independently on the two sides of the pivot, to select the first quartile on the left and the third quartile on the right.
Quickselect is probably the best solution for the interquartile range, but if the desired subsequence endpoints are closer to the ends of the array --for example, if you want to find the first and ninth decile-- then you might consider using a partial heapsort. This algorithm partitions at $V_k$ in worst-case $O(n \log k)$ (but on average, the time complexity is close to $O(n)$), as follows:
- Use heapify to turn the first $k$ elements of $V$ into a max-heap.
- For each of the remaining $n-k$ elements:
- If the element is less than the heap's maximum, swap it and the heap's maximum and repair the heap.
- Otherwise, continue.
If you build the heap backwards, so that the maximum is at position $k$, then you'll end up with $V$ correctly partitioned. (Otherwise, you'll have to swap $V_1$ and $V_k$.)
Repairing the heap at step 2 takes $O(\log k)$, but note that it doesn't always happen. In fact, assuming the dataset is randomly ordered, it happens less and less frequently as you proceed, since the heap's range shrinks each time an element is replaced making it less likely that a new element will need to be inserted.
Again, this algorithm can be adapted to find a range, by building a reversed max-heap at the beginning of the array and a forward min-heap at the end of the array, and then scanning the elements in between. This doesn't help as much as it does with quickselect, but it still helps a bit.
If you're worried about the possibility of a pathologically sorted input --not so much of a worry as it would be for quicksort, since the worst case here is log-linear rather than quadratic-- you can shuffle the input as you go by swapping each element with a randomly selected element from the unprocessed segment, in effect a single step of the Fisher-Yates shuffle algorithm. Although that makes worst-case performance extremely unlikely, it does have a practical cost, because reading a large array in random order is much less cache-friendly than reading the array sequentially.
