Funnelsort
Funnelsort is a comparison-based sorting algorithm. It was introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999 in the context of the cache oblivious model.In the external memory model, the number of memory transfers it needs to perform a sort of items on a machine with cache of size and cache lines of length is , under the tall cache assumption that . This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. Funnelsort also achieves the asymptotically optimal runtime complexity of .
primaryTopic
Funnelsort
Funnelsort is a comparison-based sorting algorithm. It was introduced by Frigo, Leiserson, Prokop, and Ramachandran in 1999 in the context of the cache oblivious model.In the external memory model, the number of memory transfers it needs to perform a sort of items on a machine with cache of size and cache lines of length is , under the tall cache assumption that . This number of memory transfers has been shown to be asymptotically optimal for comparison sorts. Funnelsort also achieves the asymptotically optimal runtime complexity of .
has abstract
Funnelsort is a comparison-bas ...... ptimal runtime complexity of .
@en
Wikipage page ID
42,794,816
Wikipage revision ID
705,485,783
subject
comment
Funnelsort is a comparison-bas ...... ptimal runtime complexity of .
@en
label
Funnelsort
@en