Search

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.

This paper discusses the expression of algorithms by flowcharts, and in particular by flowcharts without explicit go-to's (D-charts). For this purpose we introduce a machine independent definition of algorithm which is broader than usual. Our conclusion is that D- charts are in one technical sense more restrictive than general flowcharts, but not if one allows the introduction of additional variables which represent a history of control flow. The term "algorithm" is used in many different ways. Sometimes we speak of an algorithm as a process in the abstract, without reference to a particular computer. It is in this sense, for example, that we speak of the "radix exchange sort algorithm," or the "simplex algorithm." Often we identify an algorithm with a particular se- quence of instructions for a particular computer. In this paper we shall present a new definition of algorithm which emphasizes the sequence of commands associated with a particular "input." We then define the notion "expression" of algorithms by general flowcharts and flowcharts without explicit go-to's (D-charts). Some theorems are given which exhibit some of the rela- tionships between algorithms, flowcharts, and D-charts.

Some typical file structures, including some called “non-redundant,” are examined, and the methods used in FACT to sort such files are discussed.

The information-gathering aspect of sorting is considered from a theoretical viewpoint. A large class, 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 R . The Binary Tree Sort is shown to be in R and to have unique properties in this class. A vector is defined which characterizes the information-gathering efficiency of the algorithms of 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.

This paper describes the application of several new techniques for sorting fixed-length records to the problem of variable-length record sorting. The techniques have been implemented on a Sylvania 9400 computer system with 32,000 fixed-length words of memory. Specifically, the techniques sequence variable-length records of unrestricted size, produce long initial strings of data, merge strings of data at the power of T - 1, where T is the number of work tapes in a system, and do not restrict the volume of input data.

The Stein-Rose sorting algorithm for digital simulation is reexamined and reformulated in current terms. It is pointed out that the algorithm already contains within itself the means for the automatic detection of feedback loops (implicit outputs) in analog programs. The algorithm is then extended so that it can handle implicit outputs and the extended version is shown to be finite. Thus compilers for digital simulation languages utilizing the extended algorithm need not require that programmers take a priori action either to remove feedback loops from analog programs or to identify such loops to the compiler.

Owing to the increased volume of laboratory services and the shortage of skilled medical microbiologists who presently spend up to 30% of their time in clerical matters, pragmatic applications of electronic sorting techniques and computers should be considered to alleviate this problem. Moreover, surveillance of the hospital community, with particular reference to changing patterns of microbial resistance and the distribution of potentially infectious pathogens, requires detailed information which can be readily supplied by electronic sorting analysis. Mark-sense and prescored Port-A-Punch IBM cards were used to: (i) analyze antibiotic susceptibility data; (ii) tabulate total test loads according to conditions set down by the American Society for Clinical Pathologists; and (iii) to prepare a bacteriological report on the surveillance of hospital infections. After proper sorting and analysis, the cards also serve as a convenient reference file in the laboratory for pertinent information recorded by either blackening the appropriate areas (mark-sense style) or pushing out the preperforated rectangular holes with a simple inexpensive board and stylus (Port-A-Punch). No one scheme can fulfill the requirements of all laboratories or purposes, but ideas contained herein might serve as starting points for the design of similar systems in other laboratories.

A method is proposed for internal sorting which has the property that the expected time required per record, to sort n records with random keys, is a bounded function of n . Moreover the storage required in addition to that for the records is only 2 n address fields. It appears that the method may be a good choice when the number of records to be sorted is of the order of 10,000 or more. The method consists of partially sorting the records by a radix sort and completing the sort by sifting. In the radix sort, a list type of structure is used to present the distribution of the records.

The drawbacks of large, general tape sorting programs are pointed out, and a sorting subroutine is suggested as a remedy. The fundamental idea is the separation of the logic in tape sorting from the actual manipulation of external tape units by introduction of the concept of an elementary sorting loop. Examples show how common problems in sorting can be solved using the sorting loop concept. A few considerations in the design and implementation of a sorting subroutine are mentioned, and finally a measure of the efficiency of tape sorting methods is proposed.

An ordering operator that leads to the development of an algorithm for internal sorting is described. An analysis of the algorithm is presented, together with a discussion of the number of comparisons necessary for sorting. It is shown that the number of comparisons is close to the theoretically obtainable number. The sorting algorithm is a variant of the two-way merge.

The problem of analyzing and synthesizing sorting algorithms is studied. That is, given a sorting algorithm we want to investigate how it works in a step-by-step manner and consequently to assert that it indeed arranges the objects according to a certain ordering relationship, and conversely, given an ordering relationship according to which a set of objects are to be arranged, we want to determine an algorithm that will yield the desired result.

Many methods of sorting can be used in an electronic universal digital computer. Different sorting problems require different processes, not only for efficiency of sorting, but also to preserve such order as already exists in the data. The sorting methods known to the author are described in the paper, and their effectiveness is evaluated in various types of sorting problem.Since the possibility of using many different methods of sorting arose only recently, with the advent of the electronic computer, there is no generally accepted precise terminology. An attempt is made in the paper to introduce new terms where they are needed.The sorting methods described employ a digital computer with magnetic-tape external storage, and attention is given to the organization of transfers between the computer and the tapes, and the management of tape-reel changes.

A basic associative memory utilizing cryogenic circuitry is described and its functions are compared with those of previously published associative memory descriptions. The ordered-retrieval sorting algorithm is described, along with its implementation by means of a ternary interrogating counter. A sorting example is given. The sorting efficiency is discussed and an efficiency formula is given. The required additions to the basic memory are outlined. Finally, some of the basic cryotron circuits are illustrated and their operation described.

Read-backward Polyphase sorting provides more efficient use of the tapes available to a sort than most other sorting techniques. Backward Polyphase produces a continuous merging process from n - 1 tapes where n is the total number of tapes being used in the sorting process. Any of the available presorting techniques may be used in conjunction with the Polyphase merge sort provided that the presort has the capability of producing both ascending and descending strings and distributing the strings on the various tapes as required by the Polyphase Merge.

A technique for proving min-max norms of sorting algorithms is given. One new algorithm for finding the minimum and maximum elements of a set with fewest comparisons is proved optimal with this technique.

Read-backward Polyphase sorting provides more efficient use of the tapes available to a sort than most other sorting techniques. Backward Polyphase produces a continuous merging process from n - 1 tapes where n is the total number of tapes being used in the sorting process. Any of the available presorting techniques may be used in conjunction with the Polyphase merge sort provided that the presort has the capability of producing both ascending and descending strings and distributing the strings on the various tapes as required by the Polyphase Merge.

This report concerns the IBM 705, models I and II. It is a study of the machine time required by two internal sorting methods, the conventional two-way merge, and a form of the binary search, which is due to D. Mordy, of the IBM Corporation. In particular, estimates are derived for the more time-consuming machine operations of comparison of keys, loading of keys into accumulator storage, and transmission of tags. The first two operations arise in both methods; the last is peculiar to the binary search. If the exclusion of other ancillary program steps from the estimation of machine times may be regretted from a purely practical point of view, some of the intermediate estimates may be of interest in a more theoretical context.

@ describes the open problem of stable sorting with no more than 0(log2N) bits of extra space and less than 0(N2) computation time.In this paper we define the concept of a contiguent and show that a contiguent forming algorithm may be used as the basis for a stable sort. A class of such contiguent forming algorithm may be used as the basis for a stable sort. A class of such contiguent forming algorithms is described, the most naive of which requires 0(log N) bits of extra space and 0(N log2N) computation time.We also describe a stable merging algorithm which requires 0(N) time and 0(log N) bits of extra space, but which is not applicable to all cases. It is shown, however, that this merge may be combined with a contiguent compilation algorithm to yield a generally applicable stable sorting algorithm. One such combination provides the basis for a stable sorting algorithm which requires 0(N.logN.G(N)) time and 0(log N) bits of extra space. Another such combination provides the basis for a stable sorting algorithm which requires 0(N log N) time and 0(log2N) bits of extra space.

A new sorting technique is developed to order lists in which are given not the elements to be sorted, but differences between each element and its preceding one. The deltasort algorithm uses little core-memory, and is rather quick, and can be applied to endless lists.

Publisher Summary This chapter focuses on the construction of sorting plans. Sorting a set of objects means arranging the objects in such a way that a certain ordering relationship between them is satisfied. An algorithm leading to a correct arrangement of these objects is called a sorting algorithm. Given an ordering relationship according to which a set of objects is to be arranged, a procedure can be determined that can yield the desired result. The chapter discusses the problem of designing sorting algorithms. It explains how to merge a sorted list of seven integers and a sorted list of three integers.

This chapter discusses the elementary techniques of combinatorial computing such as sieving processes, sorting techniques, procedures concerned with connectedness, finite set covering, transformations, and isomorph rejection. A process in which several objects are eliminated in each of a series of well-defined steps is called a sieving process or a sieve. The chapter also discusses general-purpose computer implementation of special classes of sieves. Sorting and combinatorial computing have a trinal affinity: (1) sorting is used as a tool in many combinatorial algorithms; (2) many interesting theoretical problems of a combinatorial nature arise in connection with sorting processes; and (3) the programming of sorting procedures indeed typifies combinatorial programming.

I have been asked to report to you on the present state of the art of sorting. In order to do so, I have obtained help and information from more people than I can thank individually. My former employers, Arthur D. Little, Inc. have allowed me to spend many hours of their valuable time, and my present employers, The Farrington Manufacturing Co., of their, I am glad to say, even more valuable time, on sorting out the information received.

By analyzing an algorithm, we mean to study the performance of an algorithm including the assertion of its correctness and a determination of the cost of its execution. Although a given algorithm is often analyzed in a particular way that is most suitable for such an algorithm, we are more interested in general procedures and techniques that can be used to study the performance of classes of algorithms. To be able to talk about general analysis techniques will not only add to our understanding of the behavior of a class of algorithms but will also, in many cases, lead to useful synthesis procedures. A good example illustrating these points is the various techniques that can be used to analyze a class of sorting algorithms which can be modelled as networks made up of comparator modules. In this paper, we discuss several approaches to such an analysis problem. Moreover, synthesis procedures suggested by these analysis techniques will also be presented.

Sort/merge programs for magnetic tape computer systems are of two basic classes:Digital (or Radix) and CollationThe digital sort is useful in only a limited number of cases and is not examined in this paper.

The Magnavox Company has recently announced Magnacard, bases on the storage of information on magnetic cards, each with a capacity of 5,000 bits. These cards can be sorted and collated at speeds up to 100 cards per second and can be read at rates up to 60,000 alpha-numeric characters per second. This paper is concerned with a procedure for efficiently using such a system in sorting a group of items each of which is much smaller than the capacity of a card. The procedure is applicable to any storage medium with a fixed block length. It is based upon combining the high-speed card sorting capability of Magnacard with the high-speed computing capability of a central processor. The sorting procedure involves storage of multiple items to a card. These cards are then sorted into chains on the basis of the sorting fields of a single item on each card. The items on the resulting sets of cards then are merged by the central processor into completely sorted chains. By an alternation of such card sorts and data sorts, a completely sorted sequence is produced. Time savings over either solely computer performed sorts or solely card performed sorts are significant.

Designers of generalized library sort packages for the current and future generations of computers are faced with the challenge of developing new techniques that provide more effective use of these computers. The major concern in developing efficient sorting routines in the past has been the internal sorting techniques, that is, the methods of manipulating the data within the memory of the computer. Precise methods must, of course, be devised for each new computer design but, due to the extensive effort in this area in the past, few new internal sorting techniques have been introduced for, what are in computer terms, generations.

Sorting by means of a two-way merge has a reputation of requiring a clerically complicated and cumbersome program. This ALGOL 60 procedure demonstrates that, using recursion, an elegant and efficient algorithm can be designed, the correctness of which is easily proved [2]. Sorting n objects gives rise to a maximum recursion depth of [log 2 ( n - 1) + 2]. This procedure is particularly suitable for sorting when it is not desirable to move the n objects physically in store and the sorting criterion is not simple. In that case it is reasonable to take the number of compare operations as a measure for the speed of the algorithm. When n is an integral power of 2, this number will be comprised between ( n × log 2 n )/2 when the objects are sorted to begin with and ( n × log 2 n - n + 1) as an upper limit. When n is not an integral power of 2, the above formulas are approximate.