US3815083A — Method and arrangement for sorting record units h…

Claim 1

Independent Claim 248 words

A method for using a computer to sort a plurality of record units, each having a keyfield including a plurality of keyfield bits arranged in descending order of significance, comprising the steps of: a. generating a plurality of electrical signals representing record unit addresses each addressing a corresponding one of said record units, said addresses being initially arranged in an arbitrary sequence with respect to the keyfield values of the record units with which they are respectively associated; b. separating said record unit addresses into two groups of addresses, said groups comprising respectively all addresses corresponding to record units having a most significant keyfield bit of 0 and 1; c. separating each of said two groups of addresses into two subgroups of addresses in accordance with 0 and 1 values in the keyfield bit position following said most significant keyfield bit in said descending order of significance; d. associating with the addresses comprising each sub-group and indicator reflective of the preceding source group from which said addresses were derived. e. repeating the steps of forming successive pairs of sub-groups of addresses in accordance with keyfield bit values of successively decreasing significance and modifying the indicator associated with the addresses contained therein to reflect the source of said addresses until the least significant bit position in said record unit keyfields has been examined and a sequence of said addresses ordered according to said indicator numbers corresponds to a sequence of said record units ordered according to said keyfield values.

Claim 2

Independent Claim 248 words

A method for using a computer to sort a plurality of record units, each having a keyfield including a plurality of keyfield bits arranged in descending order of significance, comprising the steps of: a. generating a plurality of electrical signals representing record unit addresses each addressing a corresponding one of said record units, said addresses being initially arranged in an arbitrary sequence with respect to the keyfield values of the record units with which they are respectively associated; b. separating said record unit addresses into two groups of addresses, said groups comprising respectively all addresses corresponding to record units having a most significant keyfield bit of 0 and 1; c. separating each of said two groups of addresses into two subgroups of addresses in accordance with 0 and 1 values in the keyfield bit position following said most significant keyfield bit in said descending order of significance; d. associating with the addresses comprising each sub-group and indicator reflective of the preceding source group from which said addresses were derived. e. repeating the steps of forming successive pairs of sub-groups of addresses in accordance with keyfield bit values of successively decreasing significance and modifying the indicator associated with the addresses contained therein to reflect the source of said addresses until the least significant bit position in said record unit keyfields has been examined and a sequence of said addresses ordered according to said indicator numbers corresponds to a sequence of said record units ordered according to said keyfield values.

Claim 3

Dependent Claim 100 words

A method as set forth in claim 1 wherein said step of separating said record unit addresses into two groups comprises furnishing the most significant bit of all record units substantially simultaneously, each in a corresponding keyfield bit location addressable by the corresponding record unit address; reading out the most significant keyfield bit corresponding to each of said record unit addresses; and transferring record unit addresses having a most significant keyfield bit of 0 to a first one of said groups and record unit addresses having a most significant keyfield bit of 1 to a second one of said groups.

Claim 4

Dependent Claim 81 words

A method as set forth in claim 2, wherein transferring said record unit addresses to said first group comprises storing said record unit addresses in consecutively addressable storage locations following a first 0 assigned storage location, said so-filled storage locations constituting first 0 locations; and wherein transferring said record unit addresses to said second group comprises storing said record unit addresses in consecutively addressable storage locations following a first 1 assigned storage location, said so-filled storage locations constituting first 1 locations.

Claim 5

Dependent Claim 108 words

A method as set forth in claim 3, wherein separating each of said groups into two sub-groups comprises consecutively addressing said firsT 0 locations and said first 1 locations; transferring record units stored therein having an associated keyfield bit of 0 to consecutively addressable storage locations following a second 0 assigned storage location, said so-filled storage locations constituting second 0 locations and transferring record unit addresses stored therein having an associated keyfield bit of 1 to consecutively addressable storage locations following a second 1 assigned storage location, said so-filled storage locations constituting second 1 locations; and storing said indicator in association with each record unit address transferred .

Claim 6

Dependent Claim 21 words

A method as set forth in claim 4, wherein said indicator is the same indicator for each of said record units.

Claim 7

Dependent Claim 77 words

A method as set forth in claim 5, further comprising additional transfers of said record unit addresses between said first and second 0 and 1 locations, each under control of keyfield bit of the next lower order of significance in said descending order of significance; further comprising the step of increasing said indicator associated with a record unit address by a predetermined increment each time said record unit address is transferred from one of said 1 locations.

Claim 8

Dependent Claim 39 words

A method as set forth in claim 6, wherein the order of addressing said locations during each of said transfers is determined at least in part by the indicators associated with the record unit addresses stored in said locations.

Claim 9

Independent Claim 236 words

A system of sorting a plurality of record units, each having a keyfield, each of said keyfields comprising a plurality of keyfield bits arranged in descending order of significance, comprising, in combination, register means, storing said keyfield bits in addressable register locations; first and second record unit address storage means; input means operatively associated with said first record unit address storage means for furnishing record unit addresses in an arbitrary sequence with respect to keyfield value and for entering said record unit addresses, each providing access to a corresponding record unit, into said first record unit address storage means; register addressing means connected to said register means and said first and second record unit address storage means, for furnishing selected keyfield bits at least in part under control of said record unit addresses; and address transfer means interconnecting said first and second record unit address storage means and said register means, for transferring record unit addresses back and forth between said first and second record unit address storage means at least in part under control of said selected keyfield bits, in such a manner that the storage location of each of said record unit addresses following a transfer is a function of the 0 or 1 value of the corresponding selected keyfield bit and of the values of the keyfield bits within the same keyfield preceding said selected keyfield bit in said descending order of significance.

Claim 10

Independent Claim 236 words

A system of sorting a plurality of record units, each having a keyfield, each of said keyfields comprising a plurality of keyfield bits arranged in descending order of significance, comprising, in combination, register means, storing said keyfield bits in addressable register locations; first and second record unit address storage means; input means operatively associated with said first record unit address storage means for furnishing record unit addresses in an arbitrary sequence with respect to keyfield value and for entering said record unit addresses, each providing access to a corresponding record unit, into said first record unit address storage means; register addressing means connected to said register means and said first and second record unit address storage means, for furnishing selected keyfield bits at least in part under control of said record unit addresses; and address transfer means interconnecting said first and second record unit address storage means and said register means, for transferring record unit addresses back and forth between said first and second record unit address storage means at least in part under control of said selected keyfield bits, in such a manner that the storage location of each of said record unit addresses following a transfer is a function of the 0 or 1 value of the corresponding selected keyfield bit and of the values of the keyfield bits within the same keyfield preceding said selected keyfield bit in said descending order of significance.

Claim 11

Dependent Claim 47 words

A system as set forth in claim 8, wherein each of said addressable register locations is addressable by a corresponding one of said record unit addresses; and wherein each of said keyfield bits is stored in an addressable register location addressable by its associated record unit address.

Claim 12

Dependent Claim 16 words

A system as set forth in claim 9, wherein said register addressing means comprise multiplexer means.

Claim 13

Dependent Claim 72 words

A system as set forth in claim 10, further comprising mode control means alternately furnishing a first and second mode control signal; and wherein said address transfer means transfers said record unit addresses from said first to said second record unit address storage means in response to said first mode control signal and from said second to said first record unit address storage means in response to said second mode control signal.

Claim 14

Dependent Claim 155 words

A system as set forth in claim 10, wherein said first and second record unit address storage means have, respectively, a first and second 0 assIgned storage location and a first and second 1 assigned storage location; wherein said address transfer means comprise first address transfer means operatively associated with said first record unit address storage means, said first address transfer means comprising first and second location selecting means respectively addressing consecutively addressable storage locations following said first 0 assigned storage location and said first 1 assigned storage location in response to first and second gating output signals respectively; further comprising first gating means furnishing a first gating output signal in response to simultaneous presence of an 0 selected keyfield bit and said second mode control signal; and second gating means for furnishing a second gating output signal in response to simultaneous presence of a 1 selected keyfield bit and said second mode control signal.

Claim 15

Dependent Claim 85 words

A system as set forth in claim 12, wherein said first record unit address storage means has a plurality of location selector inputs; wherein said first and second location selecting means comprise first and second counting means; further comprising second multiplexer means having second multiplexer inputs connected to the outputs of said first and second counting means and furnishing location selector signals to said location selector inputs of said first record unit address storage means in correspondence with signals applied at said second multiplexer inputs.

Claim 16

Dependent Claim 52 words

A system as set forth in claim 13, wherein location selector signals corresponding to signals furnished by said first counting means select locations following said first 0 assigned storage location, and location selector signals corresponding to signals furnished by said second counting means select locations following said first 1 assigned storage location.

Claim 17

Dependent Claim 122 words

A system as set forth in claim 14, further comprising group number storage means operatively associated with said first record unit address storage means, said group number storage means having a plurality of group number storage locations corresponding in number to the number of storage locations in said first record unit address storage means, each for storing a group number associated with the one of said record unit addresses stored in the corresponding one of said record unit address storage locations; and group location selector means interconnected between said first and second counting means and said group number storage means for addressing storage locations in said group number storage means in dependence on signals furnished by said first and second counting means.

Claim 18

Dependent Claim 18 words

A system as set forth in claim 15, wherein said group location selector means comprise third multiplexer means.

Claim 19

Dependent Claim 50 words

A system as set forth in claim 15, wherein said group number storage means comprise a data input; further comprising group number counting means having a group number output connected to said data input, and a group counter input; further comprising third gating means connected to said group counter input.

Claim 20

Dependent Claim 65 words

A system as set forth in claim 17, further comprising comparator means having a first comparator input connected to the output of said group number storage means, a second comparator input connected to the output of said group number counting means, and a comparator output furnishing a first comparator output signal indicative of equal inputs and a second comparator output signal indicative of unequal inputs.

Claim 21

Dependent Claim 43 words

A system as set forth in claim 18, further comprising first and second flip-flop means, each having a reset enable input connected to said second comparator output, a set enable input connected to said first comparator output, and a set and reset output.

Claim 22

Dependent Claim 102 words

A system as set forth in claim 19, further comprising fourth gating means having an output connected to said first counting means and furnishing one of said first gating output signals in response to simultaneous presence of said first mode control signAl and said set output of said first flip-flop means; also comprising fifth gating means having an output connected to said second counting means and furnishing one of said second gating output signals in response to simultaneous presence of said first mode control signal, said set output of said second flip-flop means and said reset output of said first flip-flop means.

Claim 23

Dependent Claim 151 words

A system as set forth in claim 20, wherein said second multiplexer means have a first and second enable input, signals applied at said first and second enable inputs enabling second multiplexer inputs connected to said first and second counting outputs respectively; and wherein said second multiplexer means further comprise second multiplexer gating means having an output connected to said first enable input of said second multiplexer means, a first input connected to the output of said first gating means and a second input connected to said set output of said first flip-flop means; and wherein said second multiplexer means further comprise additional second multiplexer gating means having an output connected to said second enable input, a first input connected to the output of said second gating means and a second input connected to said set output of said second flip-flop means and said reset output of said first flip-flop means.

Claim 24

Dependent Claim 38 words

A system as set forth in claim 19, further comprising means for furnishing a group counter advance pulse in response to a change in said first or said second flip-flop means from a set to a reset state.

Claim 25

Dependent Claim 59 words

A system as set forth in claim 22, further comprising timing signal furnishing means furnishing bit time signals; and means interconnecting said mode control means and said timing signal furnishing means in such a manner that said mode control means furnish said first and second mode control signal alternately in response to consecutive ones of said bit time signals.

Claim 26

Dependent Claim 50 words

A system as set forth in claim 23, wherein said timing signal furnishing means further furnish a plurality of subbit time signals at predetermined substantially equal intervals between consecutive ones of said bit time signals, the interval between consecutive ones of said subbit time signals constituting a subbit time interval.

Claim 27

Dependent Claim 46 words

A system as set forth in claim 24, further comprising register input means for entering into said register means, in sequence, a plurality of sets of keyfield bits, each of said sets comprising a keyfield bit of the same significance from each of said record units.

Claim 28

Dependent Claim 46 words

A system as set forth in claim 25, wherein said register means comprise a plurality of addressable register locations corresponding in number to the number of said record unit addresses; and wherein each of said addressable register locations is addressable by a corresponding record unit address.

Claim 29

Dependent Claim 47 words

A system as set forth in claim 26, further comprising means for applying said subbit time signals to said register input means for timing the operation thereof in such a manner that, for each of said subbit time signals, a set of said keyfield bits is entered.

Claim 30

Dependent Claim 83 words

A system as set forth in claim 27, wherein said means for furnishing timing signals further comprise means for furnishing, within each of said subbit time intervals, first additional timing signals, applied in a predetermined sequence in time to said second enable input of said third multiplexer means, said first flip-flop means, said first enable input of said third multiplexer means, and said second flip-flop means, thereby setting said first and second flip-flop means for furnishing inputs to said second multiplexer gating means.

Claim 31

Dependent Claim 46 words

A system as set forth in claim 28, wherein said means for furnishing timing signals further furnish further timing signals following said additional timing signals for timing inputs into said first and second record unit address storage means and advancing said first and second counting means.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1977-06-03	1977-12-03	1978-06-04	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1981-06-03	1981-12-03	1982-06-04	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1985-06-03	1985-12-03	1986-06-04	$7700.00	Window Closed / Lapsed

Method and arrangement for sorting record units having keyfield bits arranged in descending order of significance without comparator

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag