Sort Technique
sort (Listing Three) is an example of a common LISP technique. Self-calling LISP functions are frequently encountered. This technique, called "recursion," is available to programmers in most modern languages but is more common in LISP. Many programming problems lend themselves to recursive solutions, particularly list processing. Recursion can be a very powerful technique, but it must be used cautiously since each recursive call uses stack space and poorly contructed procedures can run through the stack. sort, however, is a recursive program that works very well.
sort checks to see if the list is empty or contains only one item. If so, its work is very easy. A list that is empty or contains only one item is already sorted, so sort just returns the list itself. Otherwise, sort splits the list, sorts each half, and merges the results. It sorts each half with sort, a procedure that we know will sort a list. Fortunately, the problem, which the recursive call to sort must handle, has been reduced by half. Eventually, the list will be either reduced to one, or empty, in which case the first statement in sort will cause the recursion to terminate. Since the problem is divided by half each time, the recursive depth is equal to the base-2 logarithm of the size of the list. A list of 65536 items only recurses to a depth of 16!
sort has a second parameter that is a procedure: the string-compare that was passed by main. sort is designed to sort lists consisting of different types of items. To determine the sorting order, one must be able to determine the ordering sequence for the items. For strings, string-compare(a,b) returns a value greater than zero if a comes before bin the collating order. To sort a list of items that are not strings, the user only needs to supply an appropriate compare procedure.
sort uses split to break the list into two halves. split walks two POINTERs through the list. The first POINTER is the variable 1st that was passed to split as a POINTER to the list head. Since C passes arguments by value, we are really working with a copy of the LIST variable and can use it as we wish without destroying the variable in the calling procedure. The second POINTER, tail, is stepped through the list twice as fast as the first. When tail reaches the end of the list, the first pointer, 1st, will point to the midpoint of the list. The list is pruned at this point and a POINTER to the second half of the list is returned.
Merge Procedure
merge's strategy is to build a temporary list in reverse-sorted order by pushing CONS onto the list that are selectively popped off the appropriate input list. The appropriate input list is chosen based on the compare function passed as a parameter to merge. When either of the input lists is exhausted, merge transfers the remaining items from the other list until it's empty. Finally, merge returns the reverse of the temporary list. merge manipulates CONS and thus uses cpop and cpush. This process is more efficient than using pop and push since these procedures use free and malloc to release and allocate a CONS on each call.
reverse, a procedure that reverses a list, uses cpop and cpush to change the order of the CONS in a list. Like merge, reverse pops from one list and pushes to another, yielding a list whose order is reversed from the original.
The sort program is written in ANSI-compatible C so it should be adaptable to any system. I have compiled it using Microsoft C 5.1 and a compact memory model, allowing access to all available memory under MS-DOS. Text files of over 250K can be sorted using the program (the sort program provided with MS-DOS is limited to files of 64K or less). On an 8MHz 8086 system, sorting a file of 239K bytes took 40 seconds. On an 18 MHz 80386, the same sort took less than five seconds. In general, the sort program is several times faster than the one provided with MS-DOS.
These procedures can be improved in many ways. For example, many text files contain blank lines. Each time one of these lines l is read, space is allocated to hold the '\n' (newline) character as well as the terminating '\0' (null). This problem results in numerous cases of duplicate strings that contain identical data. The storage space for a string exceeds that needed for just the characters in a string since each memory fragment required by the memory allocation scheme has overhead. If we could remove these duplicates, we could save data. For our purposes, the list, which consists of CONS with pointers to the strings, is not affected if the car cell of several CONS point to the same string. We might employ a method of searching our list of existing strings to see if we have one that matches the new one before allocating the memory for it. Another method is to recode some of the simple procedures as macros. For example, push on most systems is faster and takes less space as a macro.
The sort program gives an indication of the power of list processing for nonLISP programmers. The small set of procedures shown here provides a powerful toolbox for solving the very large class of problems that lends itself to list processing. Of course, many additions can be made to this toolbox. Try it. Or better yet, if you don't already speak LISP, learn it -- you'll be glad you did.
