It's good for statisticians--or anybody whose work depends on numerical computing, for that matter--to know something about the underlying algorithms. And this one is basic, so it's worth discussing.
Analysis
The idea is to translate a percentile, such as the first or ninety-ninth, into an order statistic. This means you need to calculate how many of your data values will be less than or equal to the percentile. There are various rules for doing so, but the details don't matter here: for a given percentile $p,$ they all come down to multiplying the data count $n$ by the proportion $p/100$ and rounding. Let $k$ be this count.
The characterization of the percentile (let's call it $x$) is that (a) $x$ is greater than or equal to $k$ or more of the data values and (b) $x$ is less than or equal to $n-k$ or more of the data values.
We can get a little more specific about this characterization when we consider the possibility of a tie for $x:$ that is, two or more of the data values equal $x.$ Consequently,
- Some number $a$ of the data values are strictly less than $x;$
- Some number $b \ge 0$ of the data values equal $x;$ and
- $a \le k \le a + b.$
It can help to think concretely about algorithms. To this end, imagine writing each of your data values on a card, one per card. This translates the preceding characterization into a physical one:
Given $n$ cards bearing numbers, split the cards from left to right into three piles of $a$, $b,$ and $n-a-b$ cards where (1) the cards in the middle pile all bear the same value $x;$ (2) numbers in the left pile do not exceed $x;$ (3) $x$ does not exceed any number in the right pile; and (4) $a\lt k$ and $a+b \ge k.$
$x$ is the desired percentile of the data.
Solution
This formulation practically describes its own solution:
Pick a number you think is likely to be close to the solution. (One good way: solve the problem of through brute force with a tiny random sample of the data and use that solution as your guess of $x.$ This will guarantee that you make progress by step 3.)
Go through all the cards, in any order, placing those less than $x$ in the left pile, those equal to $x$ (if any) in the middle pile, and those exceeding $x$ in the right pile. After completing this step, let there be $a$ cards in the left pile, $b$ cards in the middle pile, and $n-a-b$ cards in the right pile.
If $a \le k$ and $a+b\ge k$ or $a=k$ and $b=0,$ you're done: your guess $x$ satisfies the conditions to be the desired percentile. Otherwise,
- If $a \ge k$ your task becomes find the $k^\text{th}$ smallest value among the $a$ cards in the left pile. You can discard all the cards in the middle and right piles.
- If $a+b \lt k,$ your task becomes find the $k-a^\text{th}$ smallest value among the $n-a-b$ cards in the right pile. You can discard all the cards in the left and middle piles.
If you haven't found the answer, return to step (1), but with a (usually much) smaller dataset. Repeat until you have found the solution. Obviously this algorithm will terminate provided you ensure you discard at least one card in each iteration. Making a reasonable guess at step 1 will ensure this.
Discussion
When the order of the cards is initially randomized, the expected effort (number of cards to inspect and compare) is proportional to $n$ itself, because it usually takes just a few iterations--with each involving far fewer data, if you try to overestimate $x$ slightly at each stage--to locate $x.$ For large $n,$ this is more efficient than almost any sorting algorithm. (Sorting algorithms that use huge numbers of bins during the sorting can be competitive, but they require that extra storage.)
Those familiar with the basics of algorithms will recognize the strong affinity between this solution and QuickSort.
If this is not good enough, an online, dynamic percentile algorithm shows how improvements can be made by using more than three piles.
There are statistical applications of algorithmic thinking. For instance, this kind of "cut-and-divide" algorithm inspired the solution I posted at https://stats.stackexchange.com/a/35268/919 for graphing QQ plots of huge datasets, which is tantamount to adaptively finding some key percentiles in those datasets.