debug/sorter/retros.c

   1 /*
   2  *  An experiment with sorting algorithms
   3  */
   4
   5 #include "sherlock/sherlock.h"
   6 #include "lib/getopt.h"
   7 #include "lib/md5.h"
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <sys/mman.h>
  13 #include <sys/user.h>
  14
  15 struct elt {
  16   u32 key;
  17   u32 ballast[3];
  18 };
  19
  20 static struct elt *ary, *alt, **ind, *array0, *array1;
  21 static uns n = 10000000;
  22 static u32 sum;
  23
  24 static struct elt *alloc_elts(uns n)
  25 {
  26   return big_alloc(n * sizeof(struct elt));
  27 }
  28
  29 static void free_elts(struct elt *a, uns n)
  30 {
  31   big_free(a, n * sizeof(struct elt));
  32 }
  33
  34 static int comp(const void *x, const void *y)
  35 {
  36   const struct elt *xx = x, *yy = y;
  37   return (xx->key < yy->key) ? -1 : (xx->key > yy->key) ? 1 : 0;
  38 }
  39
  40 static int comp_ind(const void *x, const void *y)
  41 {
  42   const struct elt * const *xx = x, * const *yy = y;
  43   return comp(*xx, *yy);
  44 }
  45
  46 #define ASORT_PREFIX(x) as_##x
  47 #define ASORT_KEY_TYPE u32
  48 #define ASORT_ELT(i) a[i].key
  49 #define ASORT_SWAP(i,j) do { struct elt t=a[i]; a[i]=a[j]; a[j]=t; } while (0)
  50 #define ASORT_EXTRA_ARGS , struct elt *a
  51 #include "lib/arraysort.h"
  52
  53 #define ASORT_PREFIX(x) asi_##x
  54 #define ASORT_KEY_TYPE u32
  55 #define ASORT_ELT(i) ind[i]->key
  56 #define ASORT_SWAP(i,j) do { struct elt *t=ind[i]; ind[i]=ind[j]; ind[j]=t; } while (0)
  57 #include "lib/arraysort.h"
  58
  59 static void r1_sort(void)
  60 {
  61   struct elt *from = ary, *to = alt, *tmp;
  62 #define BITS 8
  63   uns cnt[1 << BITS];
  64   for (uns sh=0; sh<32; sh+=BITS)
  65     {
  66       bzero(cnt, sizeof(cnt));
  67       for (uns i=0; i<n; i++)
  68         cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
  69       uns pos = 0;
  70       for (uns i=0; i<(1<<BITS); i++)
  71         {
  72           uns c = cnt[i];
  73           cnt[i] = pos;
  74           pos += c;
  75         }
  76       ASSERT(pos == n);
  77       for (uns i=0; i<n; i++)
  78         to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
  79       ASSERT(cnt[(1 << BITS)-1] == n);
  80       tmp=from, from=to, to=tmp;
  81     }
  82   ary = from;
  83 #undef BITS
  84 }
  85
  86 static void r1b_sort(void)
  87 {
  88   struct elt *from = ary, *to = alt, *tmp;
  89 #define BITS 8
  90   uns cnt[1 << BITS], cnt2[1 << BITS];
  91   for (uns sh=0; sh<32; sh+=BITS)
  92     {
  93       if (sh)
  94         memcpy(cnt, cnt2, sizeof(cnt));
  95       else
  96         {
  97           bzero(cnt, sizeof(cnt));
  98           for (uns i=0; i<n; i++)
  99             cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
 100         }
 101       uns pos = 0;
 102       for (uns i=0; i<(1<<BITS); i++)
 103         {
 104           uns c = cnt[i];
 105           cnt[i] = pos;
 106           pos += c;
 107         }
 108       ASSERT(pos == n);
 109       bzero(cnt2, sizeof(cnt2));
 110       for (uns i=0; i<n; i++)
 111         {
 112           cnt2[(from[i].key >> (sh + BITS)) & ((1 << BITS) - 1)]++;
 113           to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
 114         }
 115       ASSERT(cnt[(1 << BITS)-1] == n);
 116       tmp=from, from=to, to=tmp;
 117     }
 118   ary = from;
 119 #undef BITS
 120 }
 121
 122 static void r1c_sort(void)
 123 {
 124   uns cnt[256];
 125   struct elt *ptrs[256], *x, *lim;
 126
 127   x = ary; lim = ary + n;
 128   bzero(cnt, sizeof(cnt));
 129   while (x < lim)
 130     cnt[x++->key & 255]++;
 131
 132 #define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 133
 134   PTRS(alt);
 135   x = ary; lim = ary + n;
 136   bzero(cnt, sizeof(cnt));
 137   while (x < lim)
 138     {
 139       cnt[(x->key >> 8) & 255]++;
 140       *ptrs[x->key & 255]++ = *x;
 141       x++;
 142     }
 143
 144   PTRS(ary);
 145   x = alt; lim = alt + n;
 146   bzero(cnt, sizeof(cnt));
 147   while (x < lim)
 148     {
 149       cnt[(x->key >> 16) & 255]++;
 150       *ptrs[(x->key >> 8) & 255]++ = *x;
 151       x++;
 152     }
 153
 154   PTRS(alt);
 155   x = ary; lim = ary + n;
 156   bzero(cnt, sizeof(cnt));
 157   while (x < lim)
 158     {
 159       cnt[(x->key >> 24) & 255]++;
 160       *ptrs[(x->key >> 16) & 255]++ = *x;
 161       x++;
 162     }
 163
 164   PTRS(ary);
 165   x = alt; lim = alt + n;
 166   while (x < lim)
 167     {
 168       *ptrs[(x->key >> 24) & 255]++ = *x;
 169       x++;
 170     }
 171 #undef PTRS
 172 }
 173
 174 #include <emmintrin.h>
 175
 176 static inline void sse_copy_elt(struct elt *to, struct elt *from)
 177 {
 178   __m128i m = _mm_load_si128((__m128i *) from);
 179   _mm_store_si128((__m128i *) to, m);
 180 }
 181
 182 static void r1c_sse_sort(void)
 183 {
 184   uns cnt[256];
 185   struct elt *ptrs[256], *x, *lim;
 186
 187   ASSERT(sizeof(struct elt) == 16);
 188   ASSERT(!((uintptr_t)alt & 15));
 189   ASSERT(!((uintptr_t)ary & 15));
 190
 191   x = ary; lim = ary + n;
 192   bzero(cnt, sizeof(cnt));
 193   while (x < lim)
 194     cnt[x++->key & 255]++;
 195
 196 #define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 197
 198   PTRS(alt);
 199   x = ary; lim = ary + n;
 200   bzero(cnt, sizeof(cnt));
 201   while (x < lim)
 202     {
 203       cnt[(x->key >> 8) & 255]++;
 204       sse_copy_elt(ptrs[x->key & 255]++, x);
 205       x++;
 206     }
 207
 208   PTRS(ary);
 209   x = alt; lim = alt + n;
 210   bzero(cnt, sizeof(cnt));
 211   while (x < lim)
 212     {
 213       cnt[(x->key >> 16) & 255]++;
 214       sse_copy_elt(ptrs[(x->key >> 8) & 255]++, x);
 215       x++;
 216     }
 217
 218   PTRS(alt);
 219   x = ary; lim = ary + n;
 220   bzero(cnt, sizeof(cnt));
 221   while (x < lim)
 222     {
 223       cnt[(x->key >> 24) & 255]++;
 224       sse_copy_elt(ptrs[(x->key >> 16) & 255]++, x);
 225       x++;
 226     }
 227
 228   PTRS(ary);
 229   x = alt; lim = alt + n;
 230   while (x < lim)
 231     {
 232       sse_copy_elt(ptrs[(x->key >> 24) & 255]++, x);
 233       x++;
 234     }
 235 #undef PTRS
 236 }
 237
 238 static void r1d_sort(void)
 239 {
 240   uns cnt[256];
 241   struct elt *ptrs[256], *x, *y, *lim;
 242
 243   ASSERT(!(n % 4));
 244
 245   x = ary; lim = ary + n;
 246   bzero(cnt, sizeof(cnt));
 247   while (x < lim)
 248     {
 249       cnt[x++->key & 255]++;
 250       cnt[x++->key & 255]++;
 251       cnt[x++->key & 255]++;
 252       cnt[x++->key & 255]++;
 253     }
 254
 255 #define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 256
 257   PTRS(alt);
 258   x = ary; y = ary+n/2; lim = ary + n/2;
 259   bzero(cnt, sizeof(cnt));
 260   while (x < lim)
 261     {
 262       cnt[(x->key >> 8) & 255]++;
 263       cnt[(y->key >> 8) & 255]++;
 264       *ptrs[x->key & 255]++ = *x;
 265       *ptrs[y->key & 255]++ = *y;
 266       x++, y++;
 267       cnt[(x->key >> 8) & 255]++;
 268       cnt[(y->key >> 8) & 255]++;
 269       *ptrs[x->key & 255]++ = *x;
 270       *ptrs[y->key & 255]++ = *y;
 271       x++, y++;
 272     }
 273
 274   PTRS(ary);
 275   x = alt; lim = alt + n;
 276   bzero(cnt, sizeof(cnt));
 277   while (x < lim)
 278     {
 279       cnt[(x->key >> 16) & 255]++;
 280       *ptrs[(x->key >> 8) & 255]++ = *x;
 281       x++;
 282       cnt[(x->key >> 16) & 255]++;
 283       *ptrs[(x->key >> 8) & 255]++ = *x;
 284       x++;
 285     }
 286
 287   PTRS(alt);
 288   x = ary; lim = ary + n;
 289   bzero(cnt, sizeof(cnt));
 290   while (x < lim)
 291     {
 292       cnt[(x->key >> 24) & 255]++;
 293       *ptrs[(x->key >> 16) & 255]++ = *x;
 294       x++;
 295       cnt[(x->key >> 24) & 255]++;
 296       *ptrs[(x->key >> 16) & 255]++ = *x;
 297       x++;
 298     }
 299
 300   PTRS(ary);
 301   x = alt; lim = alt + n;
 302   while (x < lim)
 303     {
 304       *ptrs[(x->key >> 24) & 255]++ = *x;
 305       x++;
 306       *ptrs[(x->key >> 24) & 255]++ = *x;
 307       x++;
 308     }
 309 #undef PTRS
 310 }
 311
 312 static void r2_sort(void)
 313 {
 314   struct elt *from = ary, *to = alt;
 315 #define BITS 14
 316   uns cnt[1 << BITS];
 317   bzero(cnt, sizeof(cnt));
 318   for (uns i=0; i<n; i++)
 319     cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++;
 320   uns pos = 0;
 321   for (uns i=0; i<(1<<BITS); i++)
 322     {
 323       uns c = cnt[i];
 324       cnt[i] = pos;
 325       pos += c;
 326     }
 327   ASSERT(pos == n);
 328   for (uns i=0; i<n; i++)
 329     to[cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++] = from[i];
 330   ASSERT(cnt[(1 << BITS)-1] == n);
 331
 332   pos = 0;
 333   for (uns i=0; i<(1 << BITS); i++)
 334     {
 335       as_sort(cnt[i] - pos, alt+pos);
 336       pos = cnt[i];
 337     }
 338   ary = alt;
 339 #undef BITS
 340 }
 341
 342 static void r3_sort(void)
 343 {
 344 #define BITS 10
 345 #define LEVELS 2
 346 #define BUCKS (1 << BITS)
 347 #define THRESHOLD 5000
 348 #define ODDEVEN 0
 349
 350   auto void r3(struct elt *from, struct elt *to, uns n, uns lev);
 351   void r3(struct elt *from, struct elt *to, uns n, uns lev)
 352   {
 353     uns sh = 32 - lev*BITS;
 354     uns cnt[BUCKS];
 355     bzero(cnt, sizeof(cnt));
 356     for (uns i=0; i<n; i++)
 357       cnt[(from[i].key >> sh) & (BUCKS - 1)]++;
 358     uns pos = 0;
 359     for (uns i=0; i<BUCKS; i++)
 360       {
 361         uns c = cnt[i];
 362         cnt[i] = pos;
 363         pos += c;
 364       }
 365     ASSERT(pos == n);
 366     for (uns i=0; i<n; i++)
 367 #if 1
 368       to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++] = from[i];
 369 #else
 370       sse_copy_elt(&to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++], &from[i]);
 371 #endif
 372     pos = 0;
 373     for (uns i=0; i<BUCKS; i++)
 374       {
 375         uns l = cnt[i]-pos;
 376         if (lev >= LEVELS || l <= THRESHOLD)
 377           {
 378             as_sort(l, to+pos);
 379             if ((lev % 2) != ODDEVEN)
 380               memcpy(from+pos, to+pos, l * sizeof(struct elt));
 381           }
 382         else
 383           r3(to+pos, from+pos, l, lev+1);
 384         pos = cnt[i];
 385       }
 386   }
 387
 388   r3(ary, alt, n, 1);
 389   if (ODDEVEN)
 390     ary = alt;
 391
 392 #undef ODDEVEN
 393 #undef THRESHOLD
 394 #undef BUCKS
 395 #undef LEVELS
 396 #undef BITS
 397 }
 398
 399 static inline struct elt *mrg(struct elt *x, struct elt *xl, struct elt *y, struct elt *yl, struct elt *z)
 400 {
 401   for (;;)
 402     {
 403       if (x->key <= y->key)
 404         {
 405           *z++ = *x++;
 406           if (x >= xl)
 407             goto xend;
 408         }
 409       else
 410         {
 411           *z++ = *y++;
 412           if (y >= yl)
 413             goto yend;
 414         }
 415     }
 416
 417  xend:
 418   while (y < yl)
 419     *z++ = *y++;
 420   return z;
 421
 422  yend:
 423   while (x < xl)
 424     *z++ = *x++;
 425   return z;
 426 }
 427
 428 static void mergesort(void)
 429 {
 430   struct elt *from, *to;
 431   uns lev = 0;
 432   if (1)
 433     {
 434       struct elt *x = ary, *z = alt, *last = ary + (n & ~1U);
 435       while (x < last)
 436         {
 437           if (x[0].key < x[1].key)
 438             *z++ = *x++, *z++ = *x++;
 439           else
 440             {
 441               *z++ = x[1];
 442               *z++ = x[0];
 443               x += 2;
 444             }
 445         }
 446       if (n % 2)
 447         *z = *x;
 448       lev++;
 449     }
 450   for (; (1U << lev) < n; lev++)
 451     {
 452       if (lev % 2)
 453         from = alt, to = ary;
 454       else
 455         from = ary, to = alt;
 456       struct elt *x, *z, *last;
 457       x = from;
 458       z = to;
 459       last = from + n;
 460       uns step = 1 << lev;
 461       while (x + 2*step <= last)
 462         {
 463           z = mrg(x, x+step, x+step, x+2*step, z);
 464           x += 2*step;
 465         }
 466       if (x + step < last)
 467         mrg(x, x+step, x+step, last, z);
 468       else
 469         memcpy(z, x, (byte*)last - (byte*)x);
 470     }
 471   if (lev % 2)
 472     ary = alt;
 473 }
 474
 475 static void sampsort(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
 476 {
 477 #define WAYS 256
 478   struct elt k[WAYS];
 479   uns cnt[WAYS];
 480   bzero(cnt, sizeof(cnt));
 481   for (uns i=0; i<WAYS; i++)
 482     k[i] = ar[random() % n];
 483   as_sort(WAYS, k);
 484   for (uns i=0; i<n; i++)
 485     {
 486       uns w = 0;
 487 #define FW(delta) if (ar[i].key > k[w+delta].key) w += delta
 488       FW(128);
 489       FW(64);
 490       FW(32);
 491       FW(16);
 492       FW(8);
 493       FW(4);
 494       FW(2);
 495       FW(1);
 496       wbuf[i] = w;
 497       cnt[w]++;
 498     }
 499   struct elt *y = al, *way[WAYS], *z;
 500   for (uns i=0; i<WAYS; i++)
 501     {
 502       way[i] = y;
 503       y += cnt[i];
 504     }
 505   ASSERT(y == al+n);
 506   for (uns i=0; i<n; i++)
 507     {
 508       uns w = wbuf[i];
 509       *way[w]++ = ar[i];
 510     }
 511   y = al;
 512   z = ar;
 513   for (uns i=0; i<WAYS; i++)
 514     {
 515       if (cnt[i] >= 1000)
 516         sampsort(cnt[i], y, z, dest, wbuf);
 517       else
 518         {
 519           as_sort(cnt[i], y);
 520           if (al != dest)
 521             memcpy(z, y, cnt[i]*sizeof(struct elt));
 522         }
 523       y += cnt[i];
 524       z += cnt[i];
 525     }
 526 #undef FW
 527 #undef WAYS
 528 }
 529
 530 static void samplesort(void)
 531 {
 532   byte *aux = xmalloc(n);
 533   sampsort(n, ary, alt, ary, aux);
 534   xfree(aux);
 535 }
 536
 537 static void sampsort2(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
 538 {
 539 #define WAYS 256
 540   struct elt k[WAYS];
 541   uns cnt[WAYS];
 542   bzero(cnt, sizeof(cnt));
 543   for (uns i=0; i<WAYS; i++)
 544     k[i] = ar[random() % n];
 545   as_sort(WAYS, k);
 546   struct elt *k1 = ar, *k2 = ar+1, *kend = ar+n;
 547   byte *ww = wbuf;
 548   while (k2 < kend)
 549     {
 550       uns w1 = 0, w2 = 0;
 551 #define FW1(delta) if (k1->key > k[w1+delta].key) w1 += delta
 552 #define FW2(delta) if (k2->key > k[w2+delta].key) w2 += delta
 553       FW1(128); FW2(128);
 554       FW1(64);  FW2(64);
 555       FW1(32);  FW2(32);
 556       FW1(16);  FW2(16);
 557       FW1(8);   FW2(8);
 558       FW1(4);   FW2(4);
 559       FW1(2);   FW2(2);
 560       FW1(1);   FW2(1);
 561       *ww++ = w1;
 562       *ww++ = w2;
 563       cnt[w1]++;
 564       cnt[w2]++;
 565       k1 += 2;
 566       k2 += 2;
 567     }
 568   if (k1 < kend)
 569     {
 570       uns w1 = 0;
 571       FW1(128); FW1(64); FW1(32); FW1(16);
 572       FW1(8); FW1(4); FW1(2); FW1(1);
 573       *ww++ = w1;
 574       cnt[w1]++;
 575     }
 576   struct elt *y = al, *way[WAYS], *z;
 577   for (uns i=0; i<WAYS; i++)
 578     {
 579       way[i] = y;
 580       y += cnt[i];
 581     }
 582   ASSERT(y == al+n);
 583   for (uns i=0; i<n; i++)
 584     {
 585       uns w = wbuf[i];
 586       *way[w]++ = ar[i];
 587     }
 588   y = al;
 589   z = ar;
 590   for (uns i=0; i<WAYS; i++)
 591     {
 592       if (cnt[i] >= 1000)
 593         sampsort2(cnt[i], y, z, dest, wbuf);
 594       else
 595         {
 596           as_sort(cnt[i], y);
 597           if (al != dest)
 598             memcpy(z, y, cnt[i]*sizeof(struct elt));
 599         }
 600       y += cnt[i];
 601       z += cnt[i];
 602     }
 603 #undef FW1
 604 #undef FW2
 605 #undef WAYS
 606 }
 607
 608 static void samplesort2(void)
 609 {
 610   byte *aux = xmalloc(n);
 611   sampsort2(n, ary, alt, ary, aux);
 612   xfree(aux);
 613 }
 614
 615 static void mk_ary(void)
 616 {
 617   ary = array0;
 618   alt = array1;
 619   struct MD5Context ctx;
 620   MD5Init(&ctx);
 621   u32 block[16];
 622   bzero(block, sizeof(block));
 623
 624   sum = 0;
 625   for (uns i=0; i<n; i++)
 626     {
 627 #if 1
 628       if (!(i % 4))
 629         {
 630           block[i%16] = i;
 631           MD5Transform(ctx.buf, block);
 632         }
 633       ary[i].key = ctx.buf[i%4];
 634 #else
 635       ary[i].key = i*(~0U/(n-1));
 636 #endif
 637       for (uns j=1; j<sizeof(struct elt)/4; j++)
 638         ((u32*)&ary[i])[j] = ROL(ary[i].key, 3*j);
 639       sum ^= ary[i].key;
 640     }
 641 }
 642
 643 static void chk_ary(void)
 644 {
 645   u32 s = ary[0].key;
 646   for (uns i=1; i<n; i++)
 647     if (ary[i].key < ary[i-1].key)
 648       die("Missorted at %d", i);
 649     else
 650       s ^= ary[i].key;
 651   if (s != sum)
 652     die("Corrupted");
 653 }
 654
 655 static void mk_ind(void)
 656 {
 657   mk_ary();
 658   ind = xmalloc(sizeof(struct elt *) * n);
 659   for (uns i=0; i<n; i++)
 660     ind[i] = &ary[i];
 661 }
 662
 663 static void chk_ind(void)
 664 {
 665   u32 s = ind[0]->key;
 666   for (uns i=1; i<n; i++)
 667     if (ind[i]->key < ind[i-1]->key)
 668       die("Missorted at %d", i);
 669     else
 670       s ^= ind[i]->key;
 671   if (s != sum)
 672     die("Corrupted");
 673   xfree(ind);
 674 }
 675
 676 int main(int argc, char **argv)
 677 {
 678   log_init(argv[0]);
 679
 680   int opt;
 681   uns op = 0;
 682   while ((opt = cf_getopt(argc, argv, CF_SHORT_OPTS "1", CF_NO_LONG_OPTS, NULL)) >= 0)
 683     switch (opt)
 684       {
 685       case '1':
 686         op |= (1 << (opt - '0'));
 687         break;
 688       default:
 689         die("usage?");
 690       }
 691
 692   array0 = alloc_elts(n);
 693   array1 = alloc_elts(n);
 694   for (uns i=0; i<n; i++)
 695     array0[i] = array1[i] = (struct elt) { 0 };
 696
 697   mk_ary();
 698   init_timer();
 699   for (uns i=0; i<5; i++)
 700     {
 701 #if 1
 702       memcpy(alt, ary, sizeof(struct elt) * n);
 703       memcpy(ary, alt, sizeof(struct elt) * n);
 704 #else
 705       for (uns j=0; j<n; j++)
 706         alt[j] = ary[j];
 707       for (uns j=0; j<n; j++)
 708         ary[j] = alt[j];
 709 #endif
 710     }
 711   log(L_DEBUG, "memcpy: %d", get_timer()/10);
 712
 713 #define BENCH(type, name, func) mk_##type(); init_timer(); func; log(L_DEBUG, name ": %d", get_timer()); chk_##type()
 714
 715   //BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
 716   //BENCH(ary, "arraysort", as_sort(n, ary));
 717   //BENCH(ind, "indirect qsort", qsort(ind, n, sizeof(struct elt *), comp_ind));
 718   //BENCH(ind, "indirect arraysort", asi_sort(n));
 719   //BENCH(ary, "radix1", r1_sort());
 720   //BENCH(ary, "radix1b", r1b_sort());
 721   BENCH(ary, "radix1c", r1c_sort());
 722   //BENCH(ary, "radix1c-sse", r1c_sse_sort());
 723   //BENCH(ary, "radix1d", r1d_sort());
 724   //BENCH(ary, "radix2", r2_sort());
 725   BENCH(ary, "radix3", r3_sort());
 726   //BENCH(ary, "mergesort", mergesort());
 727   //BENCH(ary, "samplesort", samplesort());
 728   //BENCH(ary, "samplesort2", samplesort2());
 729
 730   free_elts(array0, n);
 731   free_elts(array1, n);
 732   return 0;
 733 }