Sorting, trees, and measures of order
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper analyses the best methods of sorting on a digital computer using two main types, “sorting by merging” and “distribution sorting”, and a minimal tree is constructed giving the best strategy.
Abstract
This paper analyses the best methods of sorting on a digital computer. Two main types, “sorting by merging” and “distribution sorting” are considered. The strategy to be used is diagrammed by a tree. Optimum strategy is shown to depend on the order already existing in the data. Given this, a minimal tree is constructed giving the best strategy. A relation is shown between distribution sorting and decoding a set of messages, or searching for a particular message on a list. Two criteria for pre-existing order among items are established, and measures of order and disorder are defined. Analogy is shown between a measure of disorder and entropy in statistical mechanics, and between a measure of order and a measure of information.