In this paper the problem of sorting in various models of magnetic bubble memory systems is studied. Three basic parameters are of interest, namely, the number of steps to sort, the number of switches required, and the number of control states necessary for the switches. Several sorting algorithms are proposed with respective running times essentially n2, n/2, 1/2 n log2 n, 7/2 n, n log2n, respective numbers of switches essentially, 1, n, 2√n, 2√nlog2n , 1og2n, and respective numbers of control states essentially, 3, 2, 1/8 log2n, 1/8 log2n, and 3 log2n.

In this paper, we study the problem of maintaining a file in magnetic bubble memories. A memory structure with a special loop ordering scheme is proposed, in which records are stored in a balanced tree form. Algorithms for searching, insertion, and deletion are proposed. They have the property that, after each operation, the file is restored to a balanced tree form. The searching operation takes time log22 n/(2 log2 log2 n) + O(log2 n) where n is the number of records in the file, while insertion and deletion take additional log2 n + O(1) time each. This scheme, however, requires that each switch be individually settable. In the latter part of the paper, the memory is slightly modified, and a new loop ordering scheme proposed. With only two control operations, we show that searching, insertion, and deletion of records in the tree can still be done although the tree can no longer be kept in balanced form. If the tree is balanced, then searching, insertion, and deletion take only 5/2 log2 (n + 1) + O(1) time each.

Some special classes of interconnection networks for n terminals are considered, namely, partitioning networks and full switches. Constructions for them are presented. For the former, the resulting total count of (two-state) cels is n log2n + n − log2n − 1, and the maximum delay is 6 log2n − 4. For the latter, the cell count is (n/2)log2n − (n/2) and the maximum delay is 2 log2n − 1. By establishing appropriate lower bounds, we show that these networks are asymptotically optimal as far as cell count is concerned.