Sorting in Rexx

Introduction

After a thread about sorting appeared on comp.lang.rexx recently, I implemented a compendium of sorting algorithms in Rexx and ran some time trials.

These are the nicknames of the algorithms I implemented. For further details, please see the comments in the code.

The code and the tests

All the above algorithms were placed in a single file of Rexx code called sorts.rexx together with a prologue which takes care of calling the selected algorithm and timing it. The file is just over 1,000 lines long and measures a bit over 33K.

The program can either generate its own test data, in the form of random numbers (in the format 12345.67, complete with leading spaces if necessary so that all numbers are the same width), or can input data from a file (treating each file line as one item). For testing, the "-v" flag will generate a (possibly abbreviated) display of the items before and after sorting, and in any case the program will verify that the items are in order after they are sorted. This doesn't guarantee that the output contains all the input items, once each, but the sorted items can be written to a file for further analysis and so I am fairly confident that all the supplied sorting procedures work as advertised.

The algorithms were tested both on numbers (generated randomly for each individual test) and on text. The text was taken from archives of the comp.lang.rexx newsgroup; this means the data mostly consists of lines of 0 to 80 alphanumeric and symbol characters, and that the same data was used for each test. Up to 15% of the data strings were empty (blank lines).

The theory

The algorithms fall into several groups according to how efficient they are in theory.

• Algorithms which only exchange adjacent elements in the data (of which the classical example is bubble sort) must take (at least) time proportional to N-squared (where N is the number of items being sorted), because each of the N elements has to be moved on average N/2 places to its final position.
• The Shell and comb sorting algorithms (also known as `diminishing increment' algorithms) are difficult to quantify because the last pass is an N-squared algorithm but with the items already almost sorted. Knuth and others show that the number of comparisons carried out by Shell sort on average is proportional to about N^1.5 while some references say that comb sort takes time proportional to N log(N). This latter formula is probably an underestimate.
• The best general sorting algorithms (including heap, quick and merge) take time proportional to N log(N), which is the best that can theoretically be achieved if the sort is based on a binary-comparison operator (such as "<").
• The radix sorting algorithm in theory takes time proportional to the number of bytes of input which it has to examine.

In addition, some of the algorithms require extra working space (particularly the tournament sort, which needs space to store the results of all the matches, and merge sort, which needs a work-space to store one of the array halves while they are being merged together).

A summary of the average time and space complexity of each algorithm can be found in the following table. Note that the worst-case time complexity of quicksort is N², but this is very unlikely to happen in the given implementation.

The complexity of an algorithm (as shown in the above table) is not the whole story, however, because it does not take into account the constant of proportionality. For instance, the bubble sort is almost always much slower than any of the other N² algorithms because it carries out a lot of redundant comparisons on each pass through the data. With this in mind, the list in which the algorithms were introduced was given in approximate order according to how they are expected to perform (slowest first).

Of the five N² algorithms, as mentioned above, the bubble sort is generally expected to be the slowest. The bi-directional bubble sort is usually faster because it often requires fewer passes to get the elements in place: a small element near the end of the array only moves back one place for each left-to-right pass, but will traverse the whole array on a right-to-left pass. Shaker should be faster than selection, firstly because it reduces loop overhead by finding two elements on each pass, and secondly because an element is guaranteed not to be the maximum if it is already the minimum and so a comparison is saved in that case. Insertion is often the fastest of the N² algorithms because on average each element only has to be shifted half way up the array before it is in place. However, it performs more assignments than shaker, so the latter may sometimes win.

The quicksort algorithm is generally considered to be the fastest of the N log(N) methods, although heapsort is more predictable and doesn't have the N² worst-case that quicksort has. Merge sort can be an efficient algorithm, but is generally not preferred because of the extra space that it requires (which can also slow the algorithm down).

Radix sort is often claimed to be the fastest of all methods for sorting strings, but care must be taken when it is used for numbers. In compiled languages it can be used for sorting numbers stored in big-endian binary format or in IEEE floating-point format (provided the sign is handled properly), but in Rexx it cannot be used on unformatted numbers. Rexx also lets the algorithm down by not having an efficient way to fetch "the ith character of the nth string" - something that can be accessed directly in C, for example. The in-place radix sort is bound to be faster than the plain version in Rexx because there is less copying of the data involved.

The practice

Tests were carried out on two different interpreters, namely REXX/imc and IBM Object Rexx, as the different implementations may well favour the sorting methods in different ways. The actual timing data is shown below.

It was unsurprising that bubble, bubble2 and selection were the three worst methods in all cases, followed by shaker and insertion (in either order). More of a surprise in the Object Rexx tests was that it often took longer to sort short numbers than long text strings and that heapsort with 100 numbers took consistently longer than with 200 numbers! Also, some of Object Rexx's numeric tests seemed unstable (heapsort with 5000 numbers took either about 27 seconds or about 66 seconds with very few results in between; shellsort with 20000 numbers varied between 137 and 250 seconds but with no results between 170 and 220).

In general, heapsort was outperformed by quicksort on Object Rexx; however, contrary to expectations, the reverse was true on REXX/imc. Radix sorting methods were faster than both in most cases, despite the fact that they are not particularly suited to Rexx (for example, the operation `substr(str,n,1)' in REXX/imc causes the whole string `str' to be copied to a workspace before the nth character is selected).

Shell and comb sort were often surprisingly good, despite the fact that they are not true N log(N) algorithms. The tournament sorting method performed unexpectedly poorly in all cases, given that it ought to be very similar to the heapsort aside from the extra bookkeeping (it employs a similar tree structure). Possibly the extra space and/or the pattern of access used by the bookkeeping structure was a factor in dragging the performance down. It may also be the case that Rexx's DROP instruction (which is used in the tournament sorting routine to eliminate each winner) is relatively expensive to execute.

The plain merge sort performed better than its two variants in three of the four cases, possibly because each step involves straightforward moving of each array element into its final position, while the other two methods require the whole array to be reordered once the subscript pointers have been sorted (and they also require a greater number of temporary variables). However, it performed significantly worse on REXX/imc when sorting strings - probably because an assignment on REXX/imc causes the whole string to be copied, and this is faster with short subscripts than long text strings. The string merge sort is an attractive proposition because it is well suited to argument passing and Rexx's parse instruction, and it was declared the winner for sorting strings on REXX/imc. However, it performed rather worse on Object Rexx which perhaps means that this interpreter isn't so good at building strings and splitting them apart, relative to other operations. Sorting many elements using this method does require very long strings to be built and returned from functions, and this might be an inefficient use of memory.

Almost all the tests got significantly slower as the number of elements approached 50,000. The amount of memory consumed by the program was probably not enough to cause swapping, so it probably just means that both interpreters are relatively inefficient when dealing with large arrays of data.

A least-squares fit was attempted in order to express the time taken by each method in the form m·N^e for some multiplier m and exponent e. An expression of the form m·N^elog(N) was also attempted, but there was no case in which that provided a better fit. Probably the log(N) term was swamped by other factors such as the efficiency of each interpreter in dealing with arrays. The multipliers and exponents thus obtained are displayed in the table below. In most cases these values do not fit very well the inflated timings obtained with 20,000 or 50,000 elements. The multipliers are in units of microseconds.

The least exponent achieved was 1.20 (for `iradix' on Object Rexx) which is quite far from N log(N). The explanation for this is undoubtedly due to overheads within the Rexx interpreter. For example, we use a stem variable rather than a true array, and accessing a stem variable has a certain time penalty associated with it (this should be O(log(N)) in REXX/imc, but this interpreter also has other time penalties associated with modifying the value of a variable - particularly when it is one of several large arrays in memory).

It may (or may not) be relevant that while heap sort beat quick sort on REXX/imc it has a much larger multiplier. It was quicker for larger values of N because it has a lower exponent (although this isn't really explained by the theory).

A slightly surprising result is the exponent of 1.41 for the Shell sort. This is the only case in which the exponent came out less than that predicted by the theory.

The net result of this is that the attempted fit of the timing data to a simple formula in N is probably not very accurate or useful. In any case, the theory often doesn't predict a simple formula: a method described as O(N log(N)) might actually take time A·N+B·N·log(N) for some constants A and B. The N log(N) component dominates for larger values of N but the other term could influence the result significantly for the smaller values used in the tests.

Conclusions

Quicksort and heapsort are good general sorting algorithms and should be the natural choice for more than a few hundred data items. Radix sorting methods are fairly complex and do not work in all cases, but they are also fast and could be the best choice in some specialised applications. Merge sort can work well if the items are in a linked list or provided as a string of numbers, but for most applications the extra space required discounts it from being an efficient solution. For small numbers of items, combsort is the simplest and one of the fastest methods available. Insertion sort also has some merits for small datasets. Bubble sort is probably only ever useful as a programming exercise!

Numerical data

The average times (in seconds) for the program to run the various sorting algorithms are given below. Many of the tests which took more than about fifteen minutes were only run once (and the slower sorting algorithms were not tested at all on the larger data sets).

REXX/imc 1.76 was tested on a Sun Ultra-5 SparcStation running Solaris 9 on which it executes about 91,000 clauses per second.

IBM Object Rexx 2.2.0.0 was tested on a Pentium 233MMX machine running Red Hat Linux 7.3 on which it executes about 96,000 clauses per second. (By comparison, REXX/imc executes about 57,000 c.p.s. on this machine.)

(The appearance of the numbers 20008 and 50008 in the table below is due to Object Rexx's different interpretation of some "^Z" characters in the test data.)