### The Use of Information in SortingThe Use of Information in Sorting

Access Restriction
Subscribed

 Author Beus, H. Lynn Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1970 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The information-gathering aspect of sorting is considered from a theoretical viewpoint. A large class, $\textit{R,}$ of sorting algorithms is defined, based on the idea of information use. Properties of this algorithm class are developed, and it is noted that several well-known sorting algorithms are closely related to algorithms in $\textit{R}.$ The Binary Tree Sort is shown to be in $\textit{R}$ and to have unique properties in this class. A vector is defined which characterizes the information-gathering efficiency of the algorithms of $\textit{R}.$ Finally, a more general class of algorithms is defined, and some of the definitions extended to this class. Two intriguing conjectures are given which appear to require graph theory or combinatorial topology for their solution. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1970-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 17 Issue Number 3 Page Count 14 Starting Page 482 Ending Page 495

#### Open content in new tab

Source: ACM Digital Library