not necessary to test the second inequality. Consider the bucket which position falls into. That is, . By the induction hypothesis, all elements below , which includes all buckets up to , are completely classified. I.e. no elements which belong in those buckets remain in the rest of the array. Therefore, it is not possible that . The only remaining case is , which implies , Q.E.D. Incorporating this, the flashsort distribution algorithm begins with as described above and . Then proceed: If , the distribution is complete. Given , compute the bucket to which it belongs. If , then is unclassified. Copy it a temporary variable and: 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 , compute the bucket to which belongs and restart this (inner) loop with the new . is now correctly classified. Increment and restart the (outer) loop. While saving memory, Flashsort has the disadvantage that it recomputes the bucket for many already-classified elements. This is already done twice per element (once during the bucket-counting phase and a second time when moving each element), but searching for the first unclassified element requires a third computation for most elements. This could be expensive if buckets are assigned using a more complex formula than simple linear interpolation. A variant reduces the number of computations from almost to at most by taking the last unclassified element in an unfinished bucket as cycle leader: Maintain a variable identifying the first incompletely-classified bucket. Let to begin with, and when , the distribution is complete. Let . If , increment and restart this loop. (.) Compute the bucket to which belongs. If , then and we are done with bucket . Increment and restart this loop. If , the classification is trivial. Decrement and restart this loop. If , then is unclassified. Perform the same classification loop as the previous case, then restart this loop. Most elements have their buckets computed only twice, except for the final element in each bucket, which is used to detect the completion of the following bucket. A small further reduction can be achieved by maintaining a count of unclassified elements and stopping when it reaches zero. Performance The only extra memory requirements are the auxiliary vector for storing bucket bounds and the