Browse Prior Art Database

Track Interleave Sort

IP.com Disclosure Number: IPCOM000077674D
Original Publication Date: 1972-Sep-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 3 page(s) / 36K

Publishing Venue

IBM

Related People

Wensmark, S: AUTHOR

Abstract

The track interleave sorting distribution algorithm described below requires three work areas. The strings produced in phase 1 are distributed on two of the areas, the third remains empty. In phase 2 the strings in one of the areas are merged to longer strings written on the area that is empty. Thereafter, the strings in the other area are merged to the area that became empty, and so on.

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 54% of the total text.

Page 1 of 3

Track Interleave Sort

The track interleave sorting distribution algorithm described below requires three work areas. The strings produced in phase 1 are distributed on two of the areas, the third remains empty. In phase 2 the strings in one of the areas are merged to longer strings written on the area that is empty. Thereafter, the strings in the other area are merged to the area that became empty, and so on.

When producing the strings (either in phase 1 or in phase 2), they are written on tracks 1, M+1, 2M+1, ... until 1/M of the total number of strings for that area are written. Such a group of strings is called an interleave group. The next interleave group is written on tracks 2, M+2, 2M+2, ... When all strings are distributed on the area there are M interleave groups. The phase 1 sort is a block sort, producing strings of fixed length. Therefore, in phase 2 the strings to be merged, one per interleave group, start only one track apart from each other - which means reduced seek time.

Fig. 1 shows an example with 14 strings distributed on the area for a merge order of 4. The first interleave group contains three strings and spans over the tracks 1, 5 and 9. The fourth interleave group contains four strings and spans over the tracks 4, 8 and 12.

At merge time, string i from each of the interleave groups are merged together (i sequence number within the interleave groups). Thus the interleave groups will follow each other, synchronizing at string ends.

The number of tracks to bypass at track end, the interleave factor -1, is not constant all through the merge pass. As seen in Fig. 1, the interleave groups are not of equal length - some of them have additional string (if not, the total number of strings in the area is a multiple of the merge order).

Assume an area with 6 strings of 5 tracks each, distributed for a merge order of 4. Then the strings span the following tracks: String 1: 1,5,9,13,17

String 2: 2,6,10,14,18

String 3: 3,7,11,15,19 String 4: 21,23,25,27,29

String 5:...