Bead--Sort: A Natural Sorting Algorithm

Abstract

Nature is not only a source of minerals and precious stones but is also a mine of algorithms. By observing and studying natural phenomena, computer algorithms can be extracted. In this note, a simple natural phenomenon is used to design a sorting algorithm for positive integers, called here Bead-Sort. The algorithm's run- time complexity ranges from O(1) to O(S) (S is the sum of the input integers) depending on the user's perspective. Finally, three possible implementations are suggested.