utl_dpqsort

    /* Quick and dirty PRNG (xorshift) */
    static uint32_t utl_rnd()
    {
      static uint32_t rnd = 0;
      while (rnd == 0) rnd = (uint32_t)time(0);
    	rnd ^= rnd << 13;
	    rnd ^= rnd >> 17;
    	rnd ^= rnd << 5;
	    return rnd;
    }
   
    #define utl_dpqswap(a,b) do { if (a!=b) { \
                                      uint32_t sz = esz;\
                                      uint8_t  tmp8; \
                                      uint32_t tmp32; \
                                      uint8_t *pa = ((uint8_t *)a); \
                                      uint8_t *pb = ((uint8_t *)b); \
                                      while (sz >= 4) { \
                                        tmp32 = *(uint32_t *)pa; \
                                        *(uint32_t *)pa = *(uint32_t *)pb;\
                                        *(uint32_t *)pb = tmp32;\
                                        sz-=4; pa+=4; pb+=4;\
                                      }\
                                      switch (sz) {\
                                        case 3: tmp8=*pa; *pa=*pb; *pb=tmp8; pa--; pb--;\
                                        case 2: tmp8=*pa; *pa=*pb; *pb=tmp8; pa--; pb--;\
                                        case 1: tmp8=*pa; *pa=*pb; *pb=tmp8; pa--; pb--;\
                                      }\
                                    }\
                               } while (0)
                               
    #define utl_dpqptr(k)    ((uint8_t *)base+(k)*esz)
    #define utl_dpqpush(l,r) do {stack[stack_top][0]=(l); stack[stack_top][1]=(r); stack_top++; } while(0)
    #define utl_dpqpop(l,r)  do {stack_top--; l=stack[stack_top][0]; r=stack[stack_top][1];} while(0)
    
    /* Dropin replacement for qsort() using double pivot quicksort */
    void utl_dpqsort(void *base, uint32_t nel, uint32_t esz, int (*cmp)(const void *, const void *))
    {
      uint32_t left,right;
      uint8_t *leftptr, *rightptr; 
      
      uint32_t L,K,G;
      
      int32_t stack[128][2]; // Enough for 2^31 max elements in the array
      int16_t stack_top = 0;
      
      utl_dpqpush(0,nel);
      while (stack_top > 0) {
        utl_dpqpop(left, right);
        if (left < right) {
          if ((right - left) <= 16) {  // Use insertion sort
            for (int32_t i = left+1; i<=right; i++) {
              rightptr = utl_dpqptr(i);
              leftptr = rightptr - esz;
              for (int32_t j=i; j>0 && cmp(leftptr, rightptr) > 0; j--) {
                utl_dpqswap(rightptr, leftptr);
                rightptr = leftptr;
                leftptr = rightptr - esz;
              }
            }
          }
          else {
            leftptr = utl_dpqptr(left);
            rightptr = utl_dpqptr(right);
            
            /* Randomize pivot to avoid worst case (already sorted array) */
            L = left + (utl_rnd() % (right-left));
            G = left + (utl_rnd() % (right-left));
            utl_dpqswap(utl_dpqptr(L),leftptr);
            utl_dpqswap(utl_dpqptr(G),rightptr);
            
            if (cmp(leftptr, rightptr) > 0) {
              utl_dpqswap(leftptr, rightptr);
            }
            L=left+1; K=L; G=right-1;
            while (K <= G) {
              if (cmp(utl_dpqptr(K), leftptr) < 0) {
                utl_dpqswap(utl_dpqptr(K), utl_dpqptr(L));
                L++;
              }
              else if (cmp(utl_dpqptr(K), rightptr) > 0) {
                while ((cmp(utl_dpqptr(G), rightptr) > 0) && (K<G)) 
                  G--;
    
                utl_dpqswap(utl_dpqptr(K), utl_dpqptr(G));
                G--;
                if (cmp(utl_dpqptr(K), leftptr) < 0) {
                  utl_dpqswap(utl_dpqptr(K), utl_dpqptr(L));
                  L++;
                }
              }
              K++;
            }
            L--; G++;
            utl_dpqswap(leftptr, utl_dpqptr(L));
            utl_dpqswap(rightptr, utl_dpqptr(G));
            
            utl_dpqpush(G+1, right);
            utl_dpqpush(L+1, G-1);
            utl_dpqpush(left, L-1);
          }
        }
      }
    }