constant number of other variables used. Further, each element is moved (via a temporary buffer, so two move operations) only once. However, this memory efficiency comes with the disadvantage that the array is accessed randomly, so cannot take advantage of a data cache smaller than the whole array. As with all bucket sorts, performance depends critically on the balance of the buckets. In the ideal case of a balanced data set, each bucket will be approximately the same size. If the number of buckets is linear in the input size , each bucket has a constant size, so sorting a single bucket with an algorithm like insertion sort has complexity . The running time of the final insertion sorts is therefore . Choosing a value for , the number of buckets, trades off time spent classifying elements (high ) and time spent in the final insertion sort step (low ). For example, if is chosen proportional to , then the running time of the final insertion sorts is therefore . In the worst-case scenarios where almost all the elements are in a few buckets, the complexity of the algorithm is limited by the performance of the final bucket-sorting method, so degrades to . Variations of the algorithm improve worst-case performance by using better-performing sorts such as quicksort or recursive flashsort on buckets which exceed a certain size limit. For with uniformly distributed random data, flashsort is faster than heapsort for all and faster than quicksort for . It becomes about twice as fast as quicksort at . Note that these measurements were taken in the late 1990s, when memory hierarchies were much less dependent on cacheing. Due to the in situ permutation that flashsort performs in its classification process, flashsort is not stable. If stability is required, it is possible to use a second array so elements can be classified sequentially. However, in this case, the algorithm will require additional memory. See also Interpolation search, using the distribution of items for searching rather than sorting References External links Implementations of Randomized Sorting on Large Parallel Machines (1992) Implementation of Parallel Algorithms (1992) Visualization of Flashsort Sorting algorithms