 In the external memory model, the number of memory transfers it needs to perform a sort of formula_1 items on a machine with cache of size formula_2 and cache lines of length formula_3 is formula_4, under the tall cache assumption that formula_5.This number of memory transfers has been shown to be asymptotically optimal for comparison sorts.This distribution sort also achieves the asymptotically optimal runtime complexity of formula_6.