Pbit

From Wikipedia, the free encyclopedia

For the unit of data storage, see petabit

Pbit refers to a list sorting algorithm. Among its many advantages are that it is stable, linear and non-extensive.

[edit] Description

The algorithm takes ideas from both the radix sort and bucket sort. Nodes are sorted in phases, starting with the most significant bits. In each phase, nodes are distributed into buckets according to the next K bits. The lists are recursively sorted and merged at the end.

[edit] References

• Cornell University Computing and Information Science Technical Reports, 2006. Report describing Pbit and analyzing its algorithmic complexity. Moreover author compare Pbit with algorithm described by Donald E. Knuth in the third volume of 'The Art of Computer Programming' and other algorithms sorting list (MergeSort, QuickerSort).