Sortierprozesse auf elektronischen Rechenanlagen

Sorting orsequencing of data can be done well by electronic computers, but it is generally felt that — relative to punched card operating — the advances in these fields of electronic data processing are not so great as in other ones. One of the reasons for it may be that all purpose computers are used also for sorting problems while punch cards are sorted by highly specialized machinery, the well known sorter. A consequence of using an all purpose computer is the possibility of applying different sorting techniques. Hence the problem arises to decide which one is optimal in consideration of the machinery equipment and of the set of data. Such decisions demand a detailed knowledge of all sorting procedures. For that aim the author describes and gives flow charts of the followinginternal sorting techniques $$\begin{gathered} {\text{Sorting by pigeon holes}} \hfill \\ {\text{by address calculation}} \hfill \\ {\text{by inserting or sifting}} \hfill \\ {\text{by exchanging or repeated comparison}} \hfill \\ {\text{by selecting}} \hfill \\ {\text{by counting}} \hfill \\ {\text{by stratifying}} \hfill \\ {\text{by trees}} \hfill \\ {\text{by a) straight merging}} \hfill \\ {\text{by b) maximum string merging}} \hfill \\ {\text{by a) digital or radix sorting}} \hfill \\ {\text{by b) distribution}}{\text{.}} \hfill \\ \end{gathered} $$ In the following part of the paper the different techniques use compared relative to the necessary internal store, to the number of internal transfers, and to the average number of key comparisons. Some new approximations for the last number are given. Finally the problem of an optimal procedure relative to the average number of key comparisons is discussed and one technique analysed reaching the possible minimum. In a second paper general sorting procedures will be discussed, i. e. procedures where external stores are also involved.