Some aspects of sorting in two dimensions

The subject of this paper is two dimensional sorting. First we shall examine the problem of determining a lower bound on worst case time complexity of any two dimensional sorting algorithm, with regard to the definition of two dimensional sorting we are interested in. Then we shall design a sorting algorithm working on an information structure, such as to allow access to a record only through the adjacent ones. The algorithm has been implemented by computer, and we shall report the results obtained about time complexity, which turns out to be logarithic. While examining the above algorithm, we shall examine some special cases of two dimensional sorting. This research has been supported by Comitato Nazionale per le Scienze Matematiche, C.N.R., under a scholarship for a thesis in computer science, and a research grant No. 75.01035.01.