Search

Several letters to the editor are presented in response to the article on cognitive strategies and looping constructs by E. Soloway, J. Bonar and K. Ehrlich, which was published on November 1983 issue.

The article discusses the merge sort algorithm for sorting a random list of numbers. 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 efficient algorithm can be designed, the correctness of which is easily proved. 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. It is assumed that each object can in some way be uniquely identified by one of the integers from 1 to n. This correspondence has to be supplied in the call by replacing hi and lo by two integer variables. The essence of this algorithm is to be found in the procedure head. It has the duty to form an ordered chain of desired length deslen from the objects identified by count+1 through count+deslen.