BACKGROUND OF THE INVENTION Conventional text field sorting methods sometimes lead to surprising results because the data being sorted is not always correctly parsed by the sorting method. Most text field sorting methods, for instance, treat numeric data as a sequence of alphabetic characters. Accordingly, numeric data might be sorted such that the following undesirable results might be achieved: 1,100,2,200,3,300. The correct sorting of this numeric data, of course, should be: 1,2,3,100,200,300.

Conventional sorting methods have typically resolved this problem either by giving the user an option to specify that a field should be sorted numerically rather than alphabetically, or by recognizing when a field contains only numeric digits and automatically sorting the data numerically. Unfortunately, these methods do not handle the situation where a field has both alphabetic and numeric data. Accordingly, conventional methods might produce the following incorrect result for an alpha/numeric sort: Brand 1, Brand 100, Brand 2. Of course, the correct sort for mixed alphabetic and numeric data should be: Brand 1, Brand 2, and Brand 100.

Accordingly, there is a need in the art for a method that is capable of correctly sorting mixed alphabetic and numeric data in a given field. It is further desirable that the method automatically recognize mixed alphabetic and numeric data to dynamically achieve correct sort collation of alphabetic and numeric data in the field.

SUMMARY OF THE INVENTION The foregoing needs, and other needs and objectives that will become apparent from the description herein, are achieved by the present invention, which comprises, in one aspect, a method to dynamically sort a plurality of strings where the strings have numerical and non-numerical (alphabetic) content. The strings to be sorted are automatically divided into numerical and non-numerical substrings, and thereafter a substring in a predetermined position of a first string is compared to a substring in a predetermined position of a second string. Comparison of the substrings of the first string to the substrings of the second string continue until (i) a pair of substrings compare different, or (ii) both the first string and the second string run out of substrings. String comparisons continue until all strings are sorted in a logical order.

It is a further aspect of the present invention to compare an immediate successive substring to the substring in a predetermined position of the first string and an immediate successive substring to the substring in the predetermined position of the second string.

It is another aspect of the present invention to compare a non-numerical substring of the first string to a non-numerical substring of the second string based on the character code value of characters, such as an ASCII value, in each of the non-numerical substrings.

It is yet another aspect of the present invention to compare a numerical substring of the first string and a numerical substring of the second string based on the actual numerical values represented by each of the numerical substrings.

BRIEF DESCRIPTION OF THE DRAWINGS The present invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: Figure 1 is a flow chart describing the method for implementing dynamic sort collation according to the present invention.

Figure 2 is a table illustrating unsorted strings that have been divided into numeric and non-numeric substrings according to the present invention.

Figure 2A is a table where the strings of the table in Figure 2 have been sorted according to the present invention.

Figure 3 is a table illustrating the results of a sort in accordance with the present invention where the shaded areas of the table represent numeric strings.

Figure 4 is a block diagram of a computer system, which may be used in the implementation of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT A method and apparatus for dynamically sorting a plurality of strings where the strings have both numerical and non-numerical content is described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

In order to achieve proper dynamic sort collation using the method of the present invention, certain preferable rules, routine requirements and string definitions are defined.

I. General Rules The following rules are preferably applied to sorts using the method of the present invention.

1. Two strings are compared character by character and sorted in ASCII order until a character position is reached in both strings that contains numeric digits, or until the end of a string. A sort in accordance with this rule would yield the following result: "CAT"<"DOG"<"DOGGY"<"ZIGGY".

2. When strings are found to contain numeric digits, the strings are then scanned again until a non-numeric digit is found in each string. Numeric portions of strings are compared based on their actual numeric values. According to this embodiment, an initial non-numeric substring is considered greater than a numeric substring, but the opposite would be equally valid, depending on implementation. A sort in accordance with this rule would yield the following result: "1"<"2"<"10"<"20"<"100"<"Test 1"<"Test 2"<"Test 10"<"Test 20" a. With respect to floating point numbers, decimal points must follow the integer portion of the number. For instance,". 543" is not considered a floating point, but"0.543" is. Clearly, other embodiments might allow floating point numbers commencing with a decimal point. A sort in accordance with this rule would yield the following result: "10"<"10. 43" <"10. 5" b. A"+"or"-"sign before a number is considered only if it is at the beginning of each string or follows a space. Following are the results of three sorts in accordance with this rule: Sort 1 :"-5"<"-3"<"3"<"5"<"+7"<"10" Sort 2:"Size-10 oz."<"Size-15.5 oz."<"Size-20 oz." ("-"are not following spaces) Sort 3:"Temp-20C"<"Temp-15.5C" <"Temp-15C" <"Temp 10C"<"Temp +1OC" ("-""+"are following spaces) c. If two numeric portions of a string have the same value but differ in their appearance, then the one with fewer integer digits will have a lesser sort value. Otherwise, the one that is shorter in total length will have a lower sort value. A comparison result has a lesser sort value if viewed in ascending order the first input string should logically come before the second input string. A comparison result has a greater sort value if viewed in ascending order the first input string should logically come after the second input string. Following are the results of three sorts in accordance with this rule: Sort 1 :"1"<"01"<"001"<"0001" Sort 2 :"1"<"1. 0"<"1. 00"<"1. 000" Sort 3 :"00005. 90" <"0005. 900" <"005. 9000" 3. If two substrings are non-numeric, the substrings are compared using a non- numeric collator. This collator can be any conventional sort collating routine, such as the Standard C Library strcmp routine, that is transitive, commutative, and consistent. A non-numeric sort result meeting these requirements is as follows: "CAT"<"DOG"<"DOGGY"<"ZIGGY STARDUST" 4. If two substrings are numeric, the substrings are converted into numerical values ignoring any comma separators between the strings. a. A substring with a smaller numerical value compares less. For example :"- 3.2"<"-2"<"1"<"1. 5"<"2"<"10" b. Substring beginning with"+"compares greater than an otherwise identical substring without"+". For example:"5.2" <"+5.2" c. The substring with a fewer number of characters before a decimal point compares less. For example:"5.2" <"05. 2" <"005. 2" <"00005.200000" d. The substring with a fewer number of comma separators before a decimal point compares less. For example:"12345.2" <"12,345.2" e. The substring with a fewer number of decimal digits compares less. For example:"5.2" <"5. 20" <"5.20000" f. If one substring is numeric and the other substring is non-numeric then the numeric substring compares less. For example:"5.2" <"BRAND". This rule is fairly arbitrary and could be reversed depending on the implementation. Table 1 illustrates a sort in accordance with rules 1-4 above (the sort is in ascending order and starts from left to right beginning with Row 1).

Table 1. Row 1-159. 38-159.3-159-158.73-100-12 Row 2-5 000.500 0000. 5 0000. 50 0000. 9 0000.90 Row 3 00000. 5 00000. 9 1 01 0001 0001. 1 Row 4 2 3.423 3.54 3.78 10 +10 Row 5 0010 15 23 100 +100 234 Row 6 1000 Brand+2 Brand-1 Brand-2 Brand-10 Brand-20 Row 7 Brand-100 Test Test-Test-100 Test-50 1000 Row 8 Test-1 Test 5 Test + 5 Test 20 Test 20 - 2 Test 20 - 1 Row 9 Test 20 +2 Test 20-1 Test 20-rest 20-1.5 Test 20-2 Test 020-1 01 Row 10 Test 020-01 Test 20. 5 Test 100 II. Routine Requirements When applying the method of the present invention, the semantics and syntax used are preferably equivalent to that of the well-known Standard C Library's"strcmp"routine.

The strcmp routine performs a lexicographical character by character comparison of two strings that uses the ASCII ordinal value of each character. Following are the preferable routinerequirements: 1. The sort routine takes two null terminated character strings as input strings.

2. The result of the collation of the two strings will be returned by the sort routine with an integer according to the following conditions: 0 (if the first string is equivalent to the second string) -1 (if the first sting correlates"less"than the second string) +1 (if the second string correlates"less"than the first string) 3. The routine must be consistent, i. e. the result of a routine for a specific pair of strings must always be the same.

4. The routine must be transitive, i. e., if A < B and B < C then A < C.

5. The routine must be cumulative, i. e., if A = B then B = A; if A < B then B > A.

6. Two strings are equivalent if and only if the strings are character for character equivalent. For example,"5.3" is not equivalent to"05.3" or"5.30".

7. Numeric portions of strings should not be compared character-by-character according to ASCII ordinal values, but by actual numeric value. For instance,"1", "2","10","20","100"should not sort"1","10","2","20","100", as it would with a conventional sort.

8. Non-numeric portions of strings should be compared using a conventional sorting or collating routine, such as the strcmp routine.

III. String Definitions The following preferable string definitions are applicable to achieve proper dynamic sort collation.

1. A string comparison results in less if, viewed in ascending order, the first input string should logically come before the second input string.

2. A numeric substring is any consecutive portion of an input string that is accepted by one of the following definitions in a.-d. below. A numeric substring cannot be extended by adding non-numeric characters in either direction and remain accepted.

A"$"denotes the beginning of a string. A"+"or"-"must begin a string or follow a space to allow correct handling of hyphenations. For instance,"BRAND-10" (with no spaces) will compare less than"BRAND-20", whereas"TEMP-20C" (with a space) will compare less than"TEMP-1OC". Following are the preferable string definitions for a numeric substring: a. ['0'-'9'] + (',' ['0'-'9'] +) * Description: one or more consecutive numeric digits with optional comma separators.

Accepted strings under this definition:"2","345","8573823","8,583,393" Rejected strings under this definition :"2"3494",", 4933","9233," b. ['0'-'9'] + (',' ['0'-'9'] +) *.' [0'-9'] + Description: one or more consecutive numeric digits and a decimal point, followed by one or more consecutive numeric digits with optional comma separators.

Accepted strings under this definition:"2.3","0.34433","12432.1","12,432.1" Rejected strings under this definition:". 5","3.","12, 342,. 1","12342. 12,34" c. [$,''] r+', ] ['0'-'9'] + (',' ['0'-9'+) * Description: a plus or minus sign following a space or beginning a string, followed by one or more consecutive numeric digits with optional comma separators. Note that the leading space after the"$"is not included in the resulting substring.

Accepted strings under this definition:"+3.5","-3.7" d. [$,'][+',-'][0' - 9']+(,'[0' - 9']+)*.'[0' - 9'] Description: a plus or minus sign following a space or beginning a string, followed by one or more consecutive numeric digits and a decimal point, the decimal point being followed by one or more consecutive numeric digits with optional commas as separators. Note that the leading space is not included in the resulting substring.

3. A non-numeric substring is any consecutive portion of an input string that does not overlap any part of a numeric substring. The non-numeric substring cannot be extended in either direction such that it overlaps a numeric string.

IV. Method For Implementing Dynamic Sort Collation FIG. 1 is a flow chart describing the present invention's dynamic sort collation method to sort a plurality of strings having numeric and non-numeric characters. In the exemplary embodiment, beginning at block 100, each of the plurality of strings is divided into numeric and non-numeric substrings. Starting with string 1 and string 2 at block 102, string 1 consists of, from left to right, substringl l, substringl2, substringln, where n represents the rightmost substring of string 1 that must be considered to sort string 1 and string 2. String 2 consists of, from left to right, substring21, substring22, substring2n, where n represents the rightmost substring of string 2 that must be considered to sort string 1 and string 2. At block 104, if substringl l of string 1 compares different (lesser or greater) than substring21 of string 2, the result of the comparison is returned by the routine as lesser or greater at block 106. If the first pair of substrings compare equal, then the next successive leftmost substrings of each string are compared until the nth set of substrings at block 108, where a pair of substrings compare different, or where one or both of the strings run out of substrings. If the nth leftmost substrings compare different, then a lesser or greater result is produced at block 110. If one, but not both, of the strings runs out of substrings, this is equivalent to the strings comparing different under the method of the present invention, and a result of lesser or greater is returned at block 110. If the nth leftmost substrings compare equal, then string 1 and string 2 are equal and an"equal" result is returned at block 112. The steps at blocks 104 and 108 are repeated until all input strings are sorted. Accordingly, control is transferred from each of blocks 106,110 and 112 back to block 104.

Of course, while the leftmost substrings of two strings are compared first in a conventional alpha-numeric sort, comparisons may begin at any predetermined substring position if a non-conventional sort so requires without departing from the scope of the present invention. The non-conventional sort would also have to specify the position of subsequent substrings to be compared to complete the sort.

FIG. 2 is a table illustrating five non-sorted strings that are each divided into numeric and non-numeric substrings before sorting, where the numeric substrings are shaded. The order in which the full strings are compared may vary without departing from the scope of the present invention. One method is to directly compare each string to all other strings. More efficient methods, well known in the art, store the results of some comparisons, and apply well understood transitive principles to complete a sort through indirect comparisons. For example, suppose A, C and D are strings to be sorted. If A < C and D > C, then A < D. Therefore, there is no need to directly compare strings A and D.

Accordingly, the following order in which the strings of FIG. 2 are compared is not intended to limit the present invention in any way, but only serves as an example to more clearly demonstrate application of the rules, routine requirements and string definitions of the present invention. Starting with the first two strings, the substring"Los"of the first string,"Los Angeles", will compare greater than the substring"Beverly"of the second string,"Beverly Hills, CA 90210", when the strings are presented in that order using the ASCII values of the strings. Therefore, the full string"Beverly Hills, CA 90210"would come before the full string"Los Angeles"in an ascending order sort. Accordingly, there is no need to compare the next successive leftmost substrings,"Angeles"and"Hills", of the two strings.

Continuing the sort, the leftmost substring of the first string,"Los", compares greater than the leftmost substring of the third string,"1349".

The leftmost substring of the first string,"Los", compares less than the leftmost substring,"Size", of the fourth string.

The leftmost substring of both the fourth and fifth strings is"Size-"and, thus, the substrings will compare equal. The next successive leftmost strings of the two strings, "2,027.23" and"15.3", are then compared in that order. Since the two substrings are numeric, the representative numerical value of the substrings is compared, as opposed to the ASCII values used in non-numeric/non-numeric substring comparisons. Since "2,027.23" is greater than"15.3", a greater result is returned. Therefore, the fifth string will come before the fourth string in an ascending order sort.

The third full string is the only string that begins with a numeric substring,"1349", so it automatically comes before the other full strings applying the rules of the present invention. Accordingly, there is no need for direct comparisons of the third string with other strings. Taking this into account and applying transitive principles based on the comparison results, the overall ascending order sort result (viewing from top to bottom) is shown in FIG. 2A.

FIG. 3 is a table illustrating more detailed results of a dynamic sort applying the method of the present invention. To achieve the results in the table, a routine identical to the Standard C library strcmp routine would be used as the non-numeric collator. The sort starts in ascending order from left to right beginning with Row 1.

The dynamic sort routine of the present invention can be easily modified to allow for either multibyte characters, UNICODE, or collation preferences of languages other than English, including case sensitivity, by replacing the non-numeric collator. To allow case insensitivity, for example, the Standard C Library routine"stricmp"can be used in place of the strcmp routine. For language specific sorting, a locale specific sorter/collator could be used. In addition, non-English languages may require the lexical grammars for numerical values to be modified. For instance, many countries use commas for decimal places and periods as place separators.

V. Hardware Overview FIG. 4 is a block diagram that illustrates a computer system 400 upon which an embodiment of the invention may be implemented. Computer system 400 includes a bus 402 or other communication mechanism for communicating information, and a processor 403 coupled with bus 402 for processing information. Computer system 400 also includes a main memory 406, such as a random access memory (RAM) or other dynamic storage device, coupled to bus 402 for storing information and instructions to be executed by processor 403.

Main memory 406 also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 403. Computer system 400 further includes a read only memory (ROM) 408 or other static storage device coupled to bus 402 for storing static information and instructions for processor 403. A storage device 410, such as a magnetic disk or optical disk, is provided and coupled to bus 402 for storing information and instructions.

Computer system 400 may be coupled via bus 402 to a display 412, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 413, including alphanumeric and other keys, is coupled to bus 402 for communicating information and command selections to processor 403. Another type of user input device is cursor control 416, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor 403 and for controlling cursor movement on display 412. This input device typically has two degrees of freedom in two axes, a first axis (e. g., x) and a second axis (e. g., y), that allows the device to specify positions in a plane.

The invention is related to the use of computer system 400 for dynamic sort collation of a field having both alphabetic and numeric data. According to one embodiment of the invention, dynamic sort collation of alphabetic and numeric data is provided by computer system 400 in response to processor 403 executing one or more sequences of one or more instructions contained in main memory 406. Such instructions may be read into main memory 406 from another computer-readable medium, such as storage device 410. Execution of the sequences of instructions contained in main memory 406 causes processor 403 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

The term"computer-readable medium"as used herein refers to any medium that participates in providing instructions to processor 403 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device 410. Volatile media includes dynamic memory, such as main memory 406. Transmission media includes coaxial cables, copper wire and fiber optics, including the wires that comprise bus 402.

Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to processor 403 for execution. For example, the instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load the instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system 400 can receive the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal.

An infrared detector can receive the data carried in the infrared signal and appropriate circuitry can place the data on bus 402. Bus 402 carries the data to main memory 406, from which processor 403 retrieves and executes the instructions. The instructions received by main memory 406 may optionally be stored on storage device 410 either before or after execution by processor 403.

Computer system 400 also includes a communication interface 418 coupled to bus 402. Communication interface 418 provides a two-way data communication coupling to a network link 420 that is connected to a local network 422. For example, communication interface 418 may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 418 may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface 418 sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Network link 420 typically provides data communication through one or more networks to other data devices. For example, network link 420 may provide a connection through local network 422 to a host computer 423 or to data equipment operated by an Internet Service Provider (ISP) 426. ISP 426 in turn provides data communication services through the world wide packet data communication network now commonly referred to as the"Internet"428. Local network 422 and Internet 428 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 420 and through communication interface 418, which carry the digital data to and from computer system 400, are exemplary forms of carrier waves transporting the information.

Computer system 400 can send messages and receive data, including program code, through the network (s), network link 420 and communication interface 418. In the Internet example, a server 430 might transmit a requested code for an application program through Internet 428, ISP 426, local network 422 and communication interface 418. In accordance with the invention, one such downloaded application provides for overload handling as described herein.

Processor 403 may execute the received code as it is received, and/or stored in storage device 410, or other non-volatile storage for later execution. In this manner, computer system 400 may obtain application code in the form of a carrier wave.

VI. Variations, Extensions Alternately, the functionality of the invention could be achieved by performing a function on the string which converts it to a different string which, when sorted alphanumerically using a standard alphanumeric sort routine, yields the same sort order as the sorting routine of the present invention. This allows use of the invention in an environment which does not permit the sort functionality desired.

A function map () can be implemented in many ways and has the following key properties: if"a"is greater than"b"according to the rules set forth previously, then map (a) is greater than map (b) according to an alphanumeric sort.

In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.