merge.c

   1 /* In-place merging of integer sequences */
   2
   3 #define MIN(x,y) ((x)<(y) ? (x) : (y))
   4 #define SWAP(x,y) do { int _=(x); (x)=(y); (y)=_; } while(0)
   5 #define BLEN(x) ((x) == p1pos ? p1len : (x) == p2pos ? p2len : B)
   6
   7 static void reverse(int *A, int n)      // reverse a sequence
   8 {
   9         int x = 0;
  10         n--;
  11         while (x < n) {
  12                 SWAP(A[x], A[n]);
  13                 x++, n--;
  14         }
  15 }
  16
  17 static void rotate(int *A, int p, int q) // rotate a sequence
  18 {
  19         reverse(A, p);
  20         reverse(A+p, q);
  21         reverse(A, p+q);
  22 }
  23
  24 static void merge(int *A, int M, int N)
  25 {
  26         int T = M+N;                    // total length of the buffer
  27         int B = 1;                      // block size = ceil(sqrt(N))
  28         while (B*B < T)
  29                 B++;
  30
  31         int Z = MIN(B+T%B,T);           // aux buffer size
  32         int Mz=0, Nz=0;                 // find Z largest items
  33         while (Mz+Nz < Z) {
  34                 if (Mz == M || A[M-Mz-1] > A[T-Nz-1])
  35                         Mz++;
  36                 else
  37                         Nz++;
  38         }
  39         M -= Mz;                        // fix up lengths
  40         N -= Nz;
  41         rotate(A, M, Mz);               // and move the items to the beginning
  42         rotate(A, T-Nz, Nz);
  43
  44         // select-sort all blocks & track the mixed block
  45         int mixed_block = M%B ? Z+M-M%B : -1;
  46         for (int i=Z; i<T; i+=B) {
  47                 int best=i;
  48                 for (int j=i; j<T; j+=B)
  49                         if (A[j+B-1] < A[best+B-1])
  50                                 best=j;
  51                 for (int j=0; j<B; j++)
  52                         SWAP(A[i+j], A[best+j]);
  53                 if (mixed_block == i)
  54                         mixed_block = best;
  55                 else if (mixed_block == best)
  56                         mixed_block = i;
  57         }
  58
  59         // convert the mixed block to two partial ones
  60         int p1pos=-1, p1len=-1, p2pos=-1, p2len=-1;
  61         if (mixed_block >= 0) {
  62                 p1len = M%B;
  63                 p2len = B-p1len;
  64                 p1pos = Z;
  65                 while (p1pos<T && A[p1pos+B-1] <= A[mixed_block+p1len-1])
  66                         p1pos += B;
  67                 if (p1pos <= mixed_block) {
  68                         rotate(A+p1pos, mixed_block-p1pos, p1len);
  69                         p2pos = mixed_block+p1len;
  70                 } else {
  71                         rotate(A+mixed_block, p1len, p1pos-mixed_block-p1len);
  72                         p1pos -= p1len;
  73                         p2pos = mixed_block;
  74                 }
  75         }
  76
  77         // main merging pass
  78         int dest = 0;
  79         int s1 = Z;
  80         int es1 = s1;
  81         for(;;) {
  82                 while (es1 < T && (s1 == es1 || A[es1-1] <= A[es1]))
  83                         es1 += BLEN(es1);
  84                 if (es1 >= T)
  85                         break;
  86                 int s2 = es1;
  87                 int es2 = s2 + BLEN(s2);
  88                 while (s1 < es1) {
  89                         if (A[s1] <= A[s2]) {
  90                                 SWAP(A[dest], A[s1]);
  91                                 s1++;
  92                         } else {
  93                                 SWAP(A[dest], A[s2]);
  94                                 s2++;
  95                         }
  96                         dest++;
  97                 }
  98                 s1 = s2;
  99                 es1 = es2;
 100         }
 101         rotate(A+dest, Z, T-s1);
 102
 103         // sort the rest
 104         for (int i=T-Z; i<T; i++) {
 105                 int best=i;
 106                 for (int j=i+1; j<T; j++)
 107                         if (A[j] < A[best])
 108                                 best=j;
 109                 SWAP(A[i], A[best]);
 110         }
 111 }
 112
 113 #include <stdio.h>
 114 #include <time.h>
 115 #include <stdlib.h>
 116
 117 int main(void)
 118 {
 119 #if 0
 120         int A[] = { 2, 4, 8, 9, 10, 11, 13, 14, 16, 1, 5, 6, 11, 12, 15, 17, 18 };
 121         int i;
 122         merge(A, 9, 8);
 123         for (i=0; i<sizeof(A)/sizeof(A[0]); i++) printf("%d ", A[i]);
 124         putchar('\n');
 125 #else
 126         srand(time(NULL));
 127         int M = 1+random()%1000;
 128         int N = 1+random()%1000;
 129         int A[M+N];
 130         for (int i=0; i<M; i++) A[i] = (i?A[i-1]:0) + random()%100;
 131         for (int i=0; i<N; i++) A[M+i] = (i?A[M+i-1]:0) + random()%100;
 132         merge(A, M, N);
 133         for (int i=1; i<M+N; i++)
 134                 if (A[i] < A[i-1]) { puts("BUG"); return 1; }
 135         puts("OK");
 136 #endif
 137         return 0;
 138 }