of one of those variables, allowing twice as many buckets to be used and therefore half as much time spent on the final sorting. To understand it with two variables per bucket, assume there are two arrays of additional words: is the (fixed) upper limit of bucket (and ), while is a (movable) index into bucket , so . We maintain the loop invariant that each bucket is divided by into an unclassified prefix ( for have yet to be moved to their target buckets) and a classified suffix ( for are all in the correct bucket and will not be moved again). Initially and all elements are unclassified. As sorting proceeds, the are decremented until for all and all elements are classified into the correct bucket. Each round begins by finding the first incompletely classified bucket (which has ) and taking the first unclassified element in that bucket where . (Neubert calls this the "cycle leader".) Copy to a temporary variable and repeat: Compute the bucket to which belongs. Let be the location where will be stored. Exchange with , i.e. store in while fetching the previous value thereby displaced. Decrement to reflect the fact that is now correctly classified. If , restart this loop with the new . If , this round is over and find a new first unclassified element . When there are no more unclassified elements, the distribution into buckets is complete. When implemented with two variables per bucket in this way, the choice of each round's starting point is in fact arbitrary; any unclassified element may be used as a cycle leader. The only requirement is that the cycle leaders can be found efficiently. Although the preceding description uses to find the cycle leaders, it is in fact possible to do without it, allowing the entire -word array to be eliminated. (After the distribution is complete, the bucket boundaries can be found in .) Suppose that we have classified all elements up to , and are considering as a potential new cycle leader. It is easy to compute its target bucket . By the loop invariant, it is classified if , and unclassified if is outside that range. The first inequality is easy to test, but the second appears to require the value . It turns out that the induction hypothesis that all elements up to are classified implies that , so it is