1 /*
  2  * qsort.c: version 1.3 of 9/5/82
  3  * Mesa Unix C Library Source File
  4  */
  5 # ifdef SCCS
  6 static char *sccsid = "@(#)qsort.c      1.3 (NSC) 9/5/82";
  7 # endif
  8 
  9 #define STATIC
 10 
 11 STATIC int          (*qscmp)();
 12 STATIC int          qses;
 13 
 14 qsort(a, n, es, fc)
 15 char *a;
 16 unsigned n;
 17 int es;
 18 int (*fc)();
 19 {
 20           qscmp = fc;
 21           qses = es;
 22           qs1(a, a+n*es);
 23 }
 24 
 25 STATIC int
 26 qs1(a, l)
 27           char *a, *l;
 28 {
 29           register char *i, *j;
 30           register es;
 31           char **k;
 32           char *lp, *hp;
 33           int c;
 34           unsigned n;
 35 
 36 
 37           es = qses;
 38 
 39 start:
 40           if((n=l-a) <= es)
 41                     return;
 42           n = es * (n / (2*es));
 43           hp = lp = a+n;
 44           i = a;
 45           j = l-es;
 46           for(;;) {
 47                     if(i < lp) {
 48                               if((c = (*qscmp)(i, lp)) == 0) {
 49                                         qsexc(i, lp -= es);
 50                                         continue;
 51                               }
 52                               if(c < 0) {
 53                                         i += es;
 54                                         continue;
 55                               }
 56                     }
 57 
 58 loop:
 59                     if(j > hp) {
 60                               if((c = (*qscmp)(hp, j)) == 0) {
 61                                         qsexc(hp += es, j);
 62                                         goto loop;
 63                               }
 64                               if(c > 0) {
 65                                         if(i == lp) {
 66                                                   qstexc(i, hp += es, j);
 67                                                   i = lp += es;
 68                                                   goto loop;
 69                                         }
 70                                         qsexc(i, j);
 71                                         j -= es;
 72                                         i += es;
 73                                         continue;
 74                               }
 75                               j -= es;
 76                               goto loop;
 77                     }
 78 
 79 
 80                     if(i == lp) {
 81                               if(lp-a >= l-hp) {
 82                                         qs1(hp+es, l);
 83                                         l = lp;
 84                               } else {
 85                                         qs1(a, lp);
 86                                         a = hp+es;
 87                               }
 88                               goto start;
 89                     }
 90 
 91 
 92                     qstexc(j, lp -= es, i);
 93                     j = hp -= es;
 94           }
 95 }
 96 
 97 STATIC int
 98 qsexc(i, j)
 99           char *i, *j;
100 {
101           register char *ri, *rj, c;
102           int n;
103 
104           n = qses;
105           ri = i;
106           rj = j;
107           do {
108                     c = *ri;
109                     *ri++ = *rj;
110                     *rj++ = c;
111           } while(--n);
112 }
113 
114 STATIC
115 qstexc(i, j, k)
116           char *i, *j, *k;
117 {
118           register char *ri, *rj, *rk;
119           int c;
120           int n;
121 
122           n = qses;
123           ri = i;
124           rj = j;
125           rk = k;
126           do {
127                     c = *ri;
128                     *ri++ = *rk;
129                     *rk++ = *rj;
130                     *rj++ = c;
131           } while(--n);
132 }