Browse Prior Art Database

Fast Sort of Ordered, or Partially Ordered, Data

IP.com Disclosure Number: IPCOM000035175D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 2 page(s) / 55K

Publishing Venue

IBM

Related People

Arnold, HH: AUTHOR [+3]

Abstract

Sorts are generally optimized for sorting of random data. This technique provides extremely fast sorting of data that is ordered, or partially ordered, with minimal impact to the speed of sorting random data.

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

Page 1 of 2

Fast Sort of Ordered, or Partially Ordered, Data

Sorts are generally optimized for sorting of random data. This technique provides extremely fast sorting of data that is ordered, or partially ordered, with minimal impact to the speed of sorting random data.

A sort provides a capability to receive rows of data and organize them into the requested ascending or descending order. Typically, a sort has two major parts. First is the insert phase where rows of data are gotten one at a time and placed into ordered sequence strings. There are many ways of doing this. This technique applies to the sort method that creates a set of ordered pointers to the data, and then uses these pointers to physically reorder the data into sorted order on disk. The second phase is called the merge phase and is done after all rows of data are received. The merge phase takes sequence strings and merges them together into a single string of ordered data.

This technique works as follows. When Sort receives the first row of data it sets one indicator (string-order indicator) that no data has been received out of order in this sequence string. Sort also sets another indicator (total-order indicator) that no data has been received out of order for the entire sort. Each subsequent row received is compared to the previous record with the indicator remaining unchanged until a row is received out of order. If a row is received out of order, both indicators are set off and no further order checks are done in the sequence string. A sequence string with rows out of order is processed...