Sort contents
Storage.
We are required to use a stable sorting algorithm with very low, ideally zero, auxiliary storage requirement. Exchanges are generally slower than comparisons for the typical application (sorting tables, where entire rows must be exchanged whereas only entries in a single column need be compared).
In fact, we store some details in global variables for convenience and to avoid filling the stack with copies, but otherwise we will hardly need any auxiliary storage.
18Global I7S_Tab;
19Global I7S_Col;
20Global I7S_Dir;
21Global I7S_Swap;
22Global I7S_Comp;
23
24#ifdef MEASURE_SORT_PERFORMANCE;
25Global I7S_CCOUNT; Global I7S_CCOUNT2; Global I7S_XCOUNT;
26#endif;
Front End.
To perform a sort, we first call SetSortDomain to declare the swap and compare functions to be used, and then call SortArray actually to sort. (It would be nice to combine these in a single call, but I6 allows a maximum of 7 call arguments for a routine, and that would make 8.) These are the only two routines which should ever be called from outside of this template segment.
The swap and compare functions are expected to take two arguments, which are the field numbers of the fields being swapped or compared, where fields are numbered from 1. Comparison is like strcmp: it returns 0 on equality, and then is positive or negative according to which of the fields is greater in value.
43[ SetSortDomain swapf compf;
44 I7S_Swap = swapf;
45 I7S_Comp = compf;
46];
47
48[ SortArray tab col dir size test_flag algorithm;
49 I7S_Tab = tab;
50 I7S_Col = col;
51 I7S_Dir = dir;
52 #ifdef MEASURE_SORT_PERFORMANCE;
53 I7S_CCOUNT = 0;
54 I7S_CCOUNT2 = 0;
55 I7S_XCOUNT = 0;
56 #endif;
57 SortRange(0, size, algorithm);
58 #ifdef MEASURE_SORT_PERFORMANCE;
59 if (test_flag)
60 print "Sorted array of size ", size, " with ", I7S_CCOUNT2, "*10000 + ", I7S_CCOUNT,
61 " comparisons and ", I7S_XCOUNT, " exchanges^";
62 #endif;
63];
Sort Range.
This routine sorts a range of fields x ≤ i < y within the array. Fields are numbered from 0. The supplied algorithm is an I6 routine to implement a particular sorting algorithm; if it is not supplied, then in-place merge sort is used by default.
72[ SortRange x y algorithm;
73 if (y - x < 2) return;
74 if (algorithm) {
75 (algorithm)(x, y);
76 } else {
77 InPlaceMergeSortAlgorithm(x, y);
78 }
79];
Comparison and Exchange.
These are instrumented versions of how to swap and compare fields; note that the swap and compare functions are expected to number the fields from 1, not from 0. (This is convenient both for tables and lists, where rows and entries respectively are both numbered from 1.) The only access which the sorting algorithms have to the actual data being sorted is through these routines.
89[ CompareFields x y;
90 #ifdef MEASURE_SORT_PERFORMANCE;
91 I7S_CCOUNT++;
92 if (I7S_CCOUNT == 10000) { I7S_CCOUNT = 0; I7S_CCOUNT2++; }
93 #endif;
94 return I7S_Dir*I7S_Comp(I7S_Tab, I7S_Col, x+1, y+1, I7S_Dir);
95];
96
97[ ExchangeFields x y r;
98 #ifdef MEASURE_SORT_PERFORMANCE;
99 I7S_XCOUNT++;
100 if (I7S_XCOUNT < 0) { print "XO^"; I7S_XCOUNT = 0; }
101 #endif;
102 r = I7S_Swap(I7S_Tab, x+1, y+1);
103
104 return r;
105];
4W37 Sort.
We now present three alternative sorting algorithms.
The first is the one used in builds up to and including 4W37: note that this is not quite bubble sort, and that it is unstable. It is now no longer used, but is so short that we might as well keep it in the code base in case anyone needs to resurrect a very early I7 project.
116[ OldSortAlgorithm x y
117 f i j;
118 if (y - x < 2) return;
119 f = true;
120 while (f) {
121 f = false;
122 for (i=x:i<y:i++)
123 for (j=i+1:j<y:j++)
124 if (CompareFields(i, j) > 0) {
125 ExchangeFields(i, j); f = true; break;
126 }
127 }
128];
Insertion Sort.
A stable algorithm which has O(n2) running time and therefore cannot be used with large arrays, but which has good performance on nearly sorted tables, and which has very low overhead.
136[ InsertionSortAlgorithm from to
137 i j;
138 if (to > from+1) {
139 for (i = from+1: i < to: i++) {
140 for (j = i: j > from: j--) {
141 if (CompareFields(j, j-1) < 0)
142 ExchangeFields(j, j-1);
143 else break;
144 }
145 }
146 }
147];
In-Place Mergesort.
A stable algorithm with O(n log n) running time, at some stack cost, and which is generally good for nearly sorted tables, but which is also complex and has some overhead. The code here mostly follows Thomas Baudel's implementation, which in turn follows the C++ STL library.
156[ InPlaceMergeSortAlgorithm from to
157 middle;
158 if (to - from < 12) {
159 if (to - from < 2) return;
160 InsertionSortAlgorithm(from, to);
161 return;
162 }
163 middle = (from + to)/2;
164 InPlaceMergeSortAlgorithm(from, middle);
165 InPlaceMergeSortAlgorithm(middle, to);
166 IPMS_Merge(from, middle, to, middle-from, to - middle);
167];
168
169[ IPMS_Lower from to val
170 len half mid;
171 len = to - from;
172 while (len > 0) {
173 half = len/2;
174 mid = from + half;
175 if (CompareFields(mid, val) < 0) {
176 from = mid + 1;
177 len = len - half -1;
178 } else len = half;
179 }
180 return from;
181];
182
183[ IPMS_Upper from to val
184 len half mid;
185 len = to - from;
186 while (len > 0) {
187 half = len/2;
188 mid = from + half;
189 if (CompareFields(val, mid) < 0)
190 len = half;
191 else {
192 from = mid + 1;
193 len = len - half -1;
194 }
195 }
196 return from;
197];
198
199[ IPMS_Reverse from to;
200 while (from < to) {
201 ExchangeFields(from++, to--);
202 }
203];
204
205[ IPMS_Rotate from mid to
206 n val shift p1 p2;
207 if ((from==mid) || (mid==to)) return;
208 IPMS_Reverse(from, mid-1);
209 IPMS_Reverse(mid, to-1);
210 IPMS_Reverse(from, to-1);
211];
212
213[ IPMS_Merge from pivot to len1 len2
214 first_cut second_cut len11 len22 new_mid;
215 if ((len1 == 0) || (len2 == 0)) return;
216 if (len1+len2 == 2) {
217 if (CompareFields(pivot, from) < 0)
218 ExchangeFields(pivot, from);
219 return;
220 }
221 if (len1 > len2) {
222 len11 = len1/2;
223 first_cut = from + len11;
224 second_cut = IPMS_Lower(pivot, to, first_cut);
225 len22 = second_cut - pivot;
226 } else {
227 len22 = len2/2;
228 second_cut = pivot + len22;
229 first_cut = IPMS_Upper(from, pivot, second_cut);
230 len11 = first_cut - from;
231 }
232 IPMS_Rotate(first_cut, pivot, second_cut);
233 new_mid = first_cut + len22;
234 IPMS_Merge(from, first_cut, new_mid, len11, len22);
235 IPMS_Merge(new_mid, second_cut, to, len1 - len11, len2 - len22);
236];