Editing Bead sort (section)

{{Short description|Natural sorting algorithm}}
{{Multiple issues|{{refimprove|date=October 2017}}{{notability|date=October 2017}}}}
'''Bead sort''', also called '''gravity sort''', is a [[natural computing|natural]] [[sorting algorithm]], developed by [[Joshua J. Arulanandham]], [[Cristian S. Calude]] and [[Michael J. Dinneen]] in 2002, and published in ''The Bulletin of the [[European Association for Theoretical Computer Science]]''.<ref name=Arulanandham2002>{{cite web |last1=Arulanandham |first1=Joshua J. |last2=Calude |first2=Cristian S. |last3=Dinneen |first3=Michael J. |date=January 2002 |title=Bead-Sort: A Natural Sorting Algorithm |publisher=Department of Computer Science, University of Auckland |url=https://researchspace.auckland.ac.nz/bitstream/handle/2292/3679/171joshua.pdf |access-date=2021-05-14}}</ref>  Both [[Digital data|digital]] and [[analog computer|analog]] hardware [[implementation]]s of bead sort can achieve a sorting time of ''[[Big O Notation|O]]''(''n''); however, the implementation of this algorithm tends to be significantly slower in [[software]] and can only be used to sort lists of [[positive integer]]s.  Also, it would seem that even in the best case, the algorithm requires ''[[Big O Notation|O]]''(''n<sup>2</sup>'') space.