Flashsort is a distribution sorting algorithm showing linear computational complexity for uniformly distributed data sets and relatively little additional memory requirement. The original work was published in 1998 by Karl-Dietrich Neubert. Concept Flashsort is an efficient in-place implementation of histogram sort, itself a type of bucket sort. It assigns each of the input elements to one of buckets, efficiently rearranges the input to place the buckets in the correct order, then sorts each bucket. The original algorithm sorts an input array as follows: Using a first pass over the input or a priori knowledge, find the minimum and maximum sort keys. Linearly divide the range into buckets. Make one pass over the input, counting the number of elements which fall into each bucket. (Neubert calls the buckets "classes" and the assignment of elements to their buckets "classification".) Convert the counts of elements in each bucket to a prefix sum, where is the number of elements in bucket or less. ( and .) Rearrange the input to all elements of each bucket are stored in positions where . Sort each bucket using insertion sort. Steps 1–3 and 6 are common to any bucket sort, and can be improved using techniques generic to bucket sorts. In particular, the goal is for the buckets to be of approximately equal size ( elements each), with the ideal being division into quantiles. While the basic algorithm is a linear interpolation sort, if the input distribution is known to be non-uniform, a non-linear division will more closely approximate this ideal. Likewise, the final sort can use any of a number of techniques, including a recursive flash sort. What distinguishes flash sort is step 5: an efficient in-place algorithm for collecting the elements of each bucket together in the correct relative order using only words of additional memory. Memory efficient implementation The Flashsort rearrangement phase operates in cycles. Elements start out "unclassified", then are moved to the correct bucket and considered "classified". The basic procedure is to choose an unclassified element, find its correct bucket, exchange it with an unclassified element there (which must exist, because we counted the size of each bucket ahead of time), mark it as classified, and then repeat with the just-exchanged unclassified element. Eventually, the element is exchanged with itself and the cycle ends. The details are easy to understand using two (word-sized) variables per bucket. The clever part is the elimination