Browse Prior Art Database

A 1/2 n lg n Time Sorting Algorithm in Magnetic Bubble Memory

IP.com Disclosure Number: IPCOM000052832D
Original Publication Date: 1981-Jul-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 4 page(s) / 121K

Publishing Venue

IBM

Related People

Chung, KM: AUTHOR [+3]

Abstract

A switch technique is described for both the routing of bubble streams as well as routing according to their contents, e.g., a switch that can also do comparisons.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 4

A 1/2 n lg n Time Sorting Algorithm in Magnetic Bubble Memory

A switch technique is described for both the routing of bubble streams as well as routing according to their contents, e.g., a switch that can also do comparisons.

A magnetic bubble memory consists of loops of bubble domains. All the lcops are continuously circulating at the same speed in counterclockwise direction. Each bubble domain represents one bit of information. The basic information unit is a record, which consists of r bits, the first k bits of which are called the key field. The records are to be sorted according to their keys. Records can pass from one loop to the other through ""compare and steer'' switches shown in Figs. 1a and 1b placed between two loops. Each switch has four modes of operation as follows: See Original (page 1136)

Definitions: See Original

The process of sorting a bitonic sequence in order is called a bitonic sort.

Theorem 1 (Bitonic Split): If a(1)a(2)...a(n-1)a(n) (n even) ia a bitonic sequence, then the sequences See Original (1) and (2) are also bitonic sequences, and all the numbers in (1) are no larger than any number in (2).

Theorem 2: See Original

The overall organization of the sorting algorithm is illustrated in Fig. 2. There are m loops each of size h (n=hm). The loops are numbered 1, 2, ..., m. We assume that m is a power of 2. There is a switch s(i) between loop i and loop (i+l) for i = 1 to n-1.

The algorithm is best described by the example shown in Fig. 3. Line 1 is the input sequence, which is distributed among 8 loops. Line 2 shows the result of sorting individual loops. Note that odd numbered loops are sorted in a direction opposite to even n...