Data sort method utilizing finite difference tables

Claim 2

In a data processing system, a method of sorting a sequence of information items comprising the steps of a. applying to said data processing system a sequence of information items, each of said items having a numerical value, b. generating a difference table for said sequence of items, the entries of said table being generally designated by Delta km, where m designates the mth column of said table and k designates the kth row of the column, c. storing the Values of m and k associated with each negative difference of the most recently generated difference table, d. interchanging, for each stored pair of values of m and k, the (m + k)th and kth entries of said sequence if the (m + k)th entry has a value less than that of the kth entry.

Claim 3

A method as in claim 1 further comprising the steps of e. generating a new difference table for the sequence obtained at the conclusion of step (d), f. terminating said method if no negative difference is present in said new difference table, and (g) repeating steps (c) through (f) if there is a negative difference present in said new difference table.

Claim 4

A machine process for arranging a sequence of numerically valued information items in order of ascending magnitude comprising the steps of a. generating a difference table for said sequence of items, b. storing in a storage means the column number and associated row number of each negative entry of the most recently generated difference table, c. setting a variable m equal to the value of the highest valued column number stored in said storage means, d. setting a variable k equal to the value of the highest valued row number associated with said highest valued column number, e. interchanging the (m + k)th and the kth entries of said sequence if the (m + k)th entry has a value less than that of the kth entry, f. removing from said storage means the column number and associated row number corresponding to the variable m and k respectively, g. repeating steps (c) through (f) if said storage means is not empty, and h. generating a difference table for the sequence resulting from the performance of steps (a) through (g) if said storage means is empty.

Claim 5

A machine process for arranging a sequence of numerically valued information items in order of ascending magnitude comprising the steps of a. generating a difference table for said sequence of items, b. storing in a storage means the column number and associated row number of each negative entry of the most recently generated difference table, c. setting a variable m equal to the value of the highest valued column number stored in said storage means, d. setting a variable k equal to the value of the highest valued row number associated with said highest valued column number, e. interchanging the (m + k)th and the kth entries of said sequence if the (m + k)th entry has a value less than that of the kth entry, f. removing from said storage means the column number and associated row number corresponding to the variable m and k respectively, g. repeating steps (c) through (f) if said storage means is not empty, and h. generating a difference table for the sequence resulting from the performance of steps (a) through (g) if said storage means is empty.

Claim 6

A process as in claim 3 further comprising the step of repeating steps (b) through (h) until a difference table is generated which contains no negative differences.

Claim 7

In a data processing system, a process of sorting a sequence of information items in order of descending magnitude comprising the steps of a. applying to said data processing system a sequence of information items, each of said items having a numerical value, b. generating a difference table for said sequence of items, the entries of said table being generally designated by Delta km, where m designates the mth column of said table and k designates the kth row of the column, c. storing the values of m and k associated with each positive difference of the most recently generated difference table, d. interchanging, for each stored pair of values of m and k, the (m + k)th and kth entries of said sequence if the (m + k)th entry has a value greater than that of the kth entry.

Claim 8

In a data processing system, a process of sorting a sequence of information items in order of descending magnitude comprising the steps of a. applying to said data processing system a sequence of information items, each of said items having a numerical value, b. generating a difference table for said sequence of items, the entries of said table being generally designated by Delta km, where m designates the mth column of said table and k designates the kth row of the column, c. storing the values of m and k associated with each positive difference of the most recently generated difference table, d. interchanging, for each stored pair of values of m and k, the (m + k)th and kth entries of said sequence if the (m + k)th entry has a value greater than that of the kth entry.

Claim 9

A method an in claim 5 further comprising the steps of e. generating a new difference table for the sequence obtained at the conclusion of step (d), f. terminating said method if no positive difference is present in said new difference table, and g. repeating steps (c) through (f) if there is a positive difference present in said new difference table.