Оптимизация qsort

Question

Я искал самый быстрый алгоритм для сортировки 1 000 000 целых чисел. До сих пор удивительно, что встроенная функция qsort C, кажется, самая быстрая из всего, что я пробовал (я тестировал предварительно отсортированные, обратные отсортированные и случайные файлы ввода). В среднем, я получаю около 0,7 секунды для предварительной и обратной сортировки и .2 секунды для случайных.

Как я могу оптимизировать его, чтобы работать еще быстрее? Есть ли какие-нибудь быстрые трюки? Я знаю, что std-тип C++ работает быстрее, но это невозможно использовать в C ... Я привязал свой код.

int compare(const void *x, const void *y){ 
    return (*(int*)x >= *(int*)y); 
} 

qsort(list, 1000000, sizeof(int), compare); 

Answer 1

Этот подсчет/поразрядной сортировки будет сортировать 1000000 32 разрядные целые числа без знака в около 0,01 секунд на моей системе (Intel 2600K 3.4GHz), но использует второй массив (pTemp) тот же размер, что и исходный массив (pData), поэтому ему требуется в два раза больше памяти.

typedef unsigned int UI32; 

UI32 * RadixSort(UI32 * pData, UI32 * pTemp, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // index matrix 
UI32 *pDst, *pSrc, *pTmp; 
size_t i,j,m,n; 
UI32 u; 

    for(i = 0; i < count; i++){   // generate histograms 
     u = pData[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     n = 0; 
     for(i = 0; i < 256; i++){ 
      m = mIndex[j][i]; 
      mIndex[j][i] = n; 
      n += m; 
     }  
    } 
    pDst = pTemp;      // radix sort 
    pSrc = pData; 
    for(j = 0; j < 4; j++){ 
     for(i = 0; i < count; i++){ 
      u = pSrc[i]; 
      m = (size_t)(u >> (j<<3)) & 0xff; 
      pDst[mIndex[j][m]++] = u; 
     } 
     pTmp = pSrc; 
     pSrc = pDst; 
     pDst = pTmp; 
    } 
    return(pSrc); 
} 

Для целых чисел, просто нужно дополнить знаковый бит целое, когда он используется для индексирования:

typedef   int I32; 
typedef unsigned int UI32; 

I32 * RadixSort(I32 * pData, I32 * pTemp, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // index matrix 
UI32 *pDst, *pSrc, *pTmp; 
size_t i,j,m,n; 
UI32 u; 

    for(i = 0; i < count; i++){   // generate histograms 
     u = pData[i]; 
     for(j = 0; j < 4; j++){ 
      if(j != 3)     // signed integer handling 
       mIndex[j][(size_t)(u & 0xff)]++; 
      else 
       mIndex[j][(size_t)((u^0x80) & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     n = 0; 
     for(i = 0; i < 256; i++){ 
      m = mIndex[j][i]; 
      mIndex[j][i] = n; 
      n += m; 
     }  
    } 
    pDst = (UI32 *)pTemp;    // radix sort 
    pSrc = (UI32 *)pData; 
    for(j = 0; j < 4; j++){ 
     for(i = 0; i < count; i++){ 
      u = pSrc[i]; 
      if(j != 3)     // signed integer handling 
       m = (size_t)(u >> (j<<3)) & 0xff; 
      else 
       m = (size_t)((u >> (j<<3))^0x80) & 0xff; 
      pDst[mIndex[j][m]++] = u; 
     } 
     pTmp = pSrc; 
     pSrc = pDst; 
     pDst = pTmp; 
    } 
    return((I32 *)pSrc); 
}