Respondiendo a otra pregunta de Stack Overflow ( esta ), me topé con un subproblema interesante. ¿Cuál es la forma más rápida de ordenar una matriz de 6 enteros?

Como la pregunta es de muy bajo nivel:

• no podemos asumir que las bibliotecas están disponibles (y la llamada en sí tiene su costo), solo C simple
• Para evitar el vaciado de la tubería de instrucciones (que tiene un costo muy alto), probablemente deberíamos minimizar las ramas, los saltos y cualquier otro tipo de interrupción del flujo de control (como los ocultos detrás de los puntos de secuencia en &&o ||).
• el espacio es limitado y la minimización de los registros y el uso de la memoria es un problema, idealmente en el lugar es probablemente el mejor.

Realmente esta pregunta es un tipo de Golf donde el objetivo no es minimizar la longitud de la fuente sino el tiempo de ejecución. Lo llamo código 'Zening' como se usa en el título del libro Zen of Code optimization de Michael Abrash y sus secuelas .

En cuanto a por qué es interesante, hay varias capas:

• el ejemplo es simple y fácil de entender y medir, no involucra mucha habilidad C
• muestra los efectos de elección de un buen algoritmo para el problema, pero también los efectos del compilador y el hardware subyacente.

Aquí está mi implementación de referencia (ingenua, no optimizada) y mi conjunto de pruebas.

#include <stdio.h>

static __inline__ int sort6(int * d){

    char j, i, imin;
    int tmp;
    for (j = 0 ; j < 5 ; j++){
        imin = j;
        for (i = j + 1; i < 6 ; i++){
            if (d[i] < d[imin]){
                imin = i;
            }
        }
        tmp = d[j];
        d[j] = d[imin];
        d[imin] = tmp;
    }
}

static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
     return x;
}

int main(int argc, char ** argv){
    int i;
    int d[6][5] = {
        {1, 2, 3, 4, 5, 6},
        {6, 5, 4, 3, 2, 1},
        {100, 2, 300, 4, 500, 6},
        {100, 2, 3, 4, 500, 6},
        {1, 200, 3, 4, 5, 600},
        {1, 1, 2, 1, 2, 1}
    };

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6 ; i++){
        sort6(d[i]);
        /*
         * printf("d%d : %d %d %d %d %d %d\n", i,
         *  d[i][0], d[i][6], d[i][7],
         *  d[i][8], d[i][9], d[i][10]);
        */
    }
    cycles = rdtsc() - cycles;
    printf("Time is %d\n", (unsigned)cycles);
}

Resultados crudos

A medida que aumenta el número de variantes, las reuní todas en un conjunto de pruebas que se puede encontrar aquí . Las pruebas reales utilizadas son un poco menos ingenuas que las mostradas anteriormente, gracias a Kevin Stock. Puede compilarlo y ejecutarlo en su propio entorno. Estoy bastante interesado por el comportamiento en diferentes compilaciones / arquitectura de destino. (OK chicos, pónganlo en respuestas, haré +1 en cada contribuyente de un nuevo conjunto de resultados).

Le di la respuesta a Daniel Stutzbach (para jugar al golf) hace un año, ya que estaba en la fuente de la solución más rápida en ese momento (redes de clasificación).

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O2

• Llamada directa a la función de biblioteca qsort: 689.38
• Implementación ingenua (tipo de inserción): 285.70
• Tipo de inserción (Daniel Stutzbach): 142.12
• Tipo de inserción desenrollado: 125.47
• Orden de rango: 102.26
• Orden de clasificación con registros: 58.03
• Redes de clasificación (Daniel Stutzbach): 111.68
• Redes de clasificación (Paul R): 66.36
• Clasificación de redes 12 con intercambio rápido: 58.86
• Ordenar redes 12 Reordenado Swap: 53.74
• Sorting Networks 12 reordenado Simple Swap: 31.54
• Red de clasificación reordenada con intercambio rápido: 31.54
• Red de clasificación reordenada con intercambio rápido V2: 33.63
• Clasificación de burbujas en línea (Paolo Bonzini): 48.85
• Tipo de inserción desenrollada (Paolo Bonzini): 75.30

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O1

• Llamada directa a la función de biblioteca qsort: 705.93
• Implementación ingenua (tipo de inserción): 135,60
• Tipo de inserción (Daniel Stutzbach): 142.11
• Tipo de inserción desenrollado: 126.75
• Orden de rango: 46.42
• Orden de clasificación con registros: 43.58
• Redes de clasificación (Daniel Stutzbach): 115.57
• Redes de clasificación (Paul R): 64.44
• Clasificación de redes 12 con intercambio rápido: 61,98
• Ordenar redes 12 Reordenado Swap: 54.67
• Sorting Networks 12 reordenado Simple Swap: 31.54
• Red de clasificación reordenada con intercambio rápido: 31.24
• Red de clasificación reordenada con intercambio rápido V2: 33.07
• Clasificación de burbujas en línea (Paolo Bonzini): 45,79
• Tipo de inserción desenrollada (Paolo Bonzini): 80.15

Incluí los resultados de -O1 y -O2 porque, sorprendentemente, para varios programas, O2 es menos eficiente que O1. Me pregunto qué optimización específica tiene este efecto.

Comentarios sobre soluciones propuestas

Tipo de inserción (Daniel Stutzbach)

Como se esperaba, minimizar las ramas es una buena idea.

Redes de clasificación (Daniel Stutzbach)

Mejor que el tipo de inserción. Me preguntaba si el efecto principal no se obtenía al evitar el bucle externo. Lo probé mediante un tipo de inserción desenrollado para verificar y, de hecho, obtenemos aproximadamente las mismas cifras (el código está aquí ).

Redes de clasificación (Paul R)

Lo mejor por mucho. El código real que solía probar está aquí . Todavía no sé por qué es casi dos veces más rápido que la otra implementación de red de clasificación. Paso de parámetros? Max rápido?

Clasificación de redes 12 SWAP con intercambio rápido

Como sugirió Daniel Stutzbach, combiné su red de clasificación de 12 intercambios con un intercambio rápido sin ramificaciones (el código está aquí ). De hecho, es más rápido, el mejor hasta ahora con un pequeño margen (aproximadamente 5%) como se podría esperar con 1 intercambio menos.

También es interesante notar que el intercambio sin ramas parece ser mucho (4 veces) menos eficiente que el simple que usa if en la arquitectura PPC.

Llamar a la biblioteca qsort

Para dar otro punto de referencia, también intenté, como se sugiere, llamar a la biblioteca qsort (el código está aquí ). Como se esperaba, es mucho más lento: de 10 a 30 veces más lento ... como se hizo evidente con el nuevo conjunto de pruebas, el problema principal parece ser la carga inicial de la biblioteca después de la primera llamada, y no se compara tan mal con otros versión. Es solo entre 3 y 20 veces más lento en mi Linux. En algunas arquitecturas utilizadas para pruebas por otros, parece incluso más rápido (realmente estoy sorprendido por eso, ya que la biblioteca qsort usa una API más compleja).

Orden de rango

Rex Kerr propuso otro método completamente diferente: para cada elemento de la matriz, calcule directamente su posición final. Esto es eficiente porque el orden de rango de cómputo no necesita ramificación. El inconveniente de este método es que toma tres veces la cantidad de memoria de la matriz (una copia de la matriz y las variables para almacenar las órdenes de clasificación). Los resultados de rendimiento son muy sorprendentes (e interesantes). En mi arquitectura de referencia con sistema operativo de 32 bits e Intel Core2 Quad E8300, el recuento de ciclos fue ligeramente inferior a 1000 (como ordenar redes con intercambio de ramificación). Pero cuando se compiló y ejecutó en mi caja de 64 bits (Intel Core2 Duo) funcionó mucho mejor: se convirtió en el más rápido hasta ahora. Finalmente descubrí la verdadera razón. Mi caja de 32 bits usa gcc 4.4.1 y mi caja de 64 bits gcc 4.4.

actualización :

Como las cifras publicadas arriba muestran que este efecto aún se mejoró con versiones posteriores de gcc y el orden de clasificación se volvió consistentemente dos veces más rápido que cualquier otra alternativa.

Clasificación de redes 12 con intercambio reordenado

La sorprendente eficacia de la propuesta de Rex Kerr con gcc 4.4.3 me hizo preguntarme: ¿cómo podría un programa con 3 veces más uso de memoria ser más rápido que las redes de clasificación sin ramificaciones? Mi hipótesis era que tenía menos dependencias del tipo lectura después de escritura, lo que permite un mejor uso del planificador de instrucciones superescalar del x86. Eso me dio una idea: reordenar los intercambios para minimizar las dependencias de lectura después de escritura. En pocas palabras: cuando lo hace SWAP(1, 2); SWAP(0, 2);, debe esperar a que termine el primer intercambio antes de realizar el segundo porque ambos acceden a una celda de memoria común. Cuando lo hace, SWAP(1, 2); SWAP(4, 5);el procesador puede ejecutar ambos en paralelo. Lo probé y funciona como se esperaba, las redes de clasificación se ejecutan aproximadamente un 10% más rápido.

Clasificación de redes 12 con intercambio simple

Un año después de la publicación original, Steinar H. Gunderson sugirió que no deberíamos intentar burlar al compilador y mantener el código de intercambio simple. De hecho, es una buena idea ya que el código resultante es aproximadamente un 40% más rápido. También propuso un intercambio optimizado a mano utilizando el código de ensamblaje en línea x86 que aún puede ahorrar algunos ciclos más. Lo más sorprendente (dice mucho sobre la psicología del programador) es que hace un año ninguno de los usuarios intentó esa versión de intercambio. El código que solía probar está aquí . Otros sugirieron otras formas de escribir un intercambio rápido en C, pero produce el mismo rendimiento que el simple con un compilador decente.

El "mejor" código es ahora el siguiente:

static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
                    const int b = max(d[x], d[y]); \
                    d[x] = a; d[y] = b; }
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(1, 4);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}

Si creemos que nuestro conjunto de pruebas (y, sí, es bastante pobre, su simple beneficio es ser corto, simple y fácil de entender lo que estamos midiendo), el número promedio de ciclos del código resultante para un tipo es inferior a 40 ciclos ( Se ejecutan 6 pruebas). Eso coloca cada intercambio en un promedio de 4 ciclos. A eso lo llamo asombrosamente rápido. ¿Alguna otra mejora posible?

Para cualquier optimización, siempre es mejor probar, probar, probar. Intentaría al menos ordenar las redes y la inserción. Si estuviera apostando, apostaría mi dinero en el tipo de inserción basado en la experiencia pasada.

¿Sabes algo sobre los datos de entrada? Algunos algoritmos funcionarán mejor con ciertos tipos de datos. Por ejemplo, la ordenación por inserción funciona mejor en datos ordenados o casi ordenados, por lo que será la mejor opción si hay una probabilidad superior a la media de datos casi ordenados.

El algoritmo que publicó es similar a un tipo de inserción, pero parece que ha minimizado el número de intercambios a costa de más comparaciones. Sin embargo, las comparaciones son mucho más caras que los intercambios, ya que las ramas pueden hacer que la tubería de instrucciones se detenga.

Aquí hay una implementación de clasificación de inserción:

static __inline__ int sort6(int *d){
        int i, j;
        for (i = 1; i < 6; i++) {
                int tmp = d[i];
                for (j = i; j >= 1 && tmp < d[j-1]; j--)
                        d[j] = d[j-1];
                d[j] = tmp;
        }
}

Así es como construiría una red de clasificación. Primero, use este sitio para generar un conjunto mínimo de macros SWAP para una red de la longitud adecuada. Terminar eso en una función me da:

static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}

Aquí hay una implementación usando redes de clasificación :

inline void Sort2(int *p0, int *p1)
{
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;
}

inline void Sort3(int *p0, int *p1, int *p2)
{
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  
}

Realmente necesita implementaciones miny ramificaciones muy eficientes maxpara esto, ya que eso es efectivamente a lo que se reduce este código: una secuencia miny maxoperaciones (13 de cada una, en total). Lo dejo como ejercicio para el lector.

Tenga en cuenta que esta implementación se presta fácilmente a la vectorización (por ejemplo, SIMD - la mayoría de las ISA SIMD tienen instrucciones mínimas / máximas de vectores) y también a implementaciones de GPU (por ejemplo, CUDA - al no tener ramificaciones, no hay problemas con la divergencia de deformación, etc.).

Ver también: Implementación rápida del algoritmo para ordenar una lista muy pequeña

Dado que estos son enteros y las comparaciones son rápidas, ¿por qué no calcular el orden de clasificación de cada uno directamente?

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}

Parece que llegué a la fiesta un año tarde, pero aquí vamos ...

Al observar el ensamblaje generado por gcc 4.5.2, observé que se realizan cargas y almacenes para cada intercambio, lo que realmente no es necesario. Sería mejor cargar los 6 valores en los registros, ordenarlos y almacenarlos nuevamente en la memoria. Ordené que las cargas en las tiendas estuvieran lo más cerca posible de allí, los registros se necesitan primero y se usan por última vez. También utilicé la macro SWAP de Steinar H. Gunderson. Actualización: Cambié a la macro SWAP de Paolo Bonzini, que gcc se convierte en algo similar a Gunderson, pero gcc puede ordenar mejor las instrucciones, ya que no se dan como ensamblaje explícito.

Utilicé el mismo orden de intercambio que la red de intercambio reordenada dada como el mejor rendimiento, aunque puede haber un mejor orden. Si encuentro algo más de tiempo, generaré y probaré un montón de permutaciones.

Cambié el código de prueba para considerar más de 4000 arreglos y mostrar el número promedio de ciclos necesarios para ordenar cada uno. En un i5-650 obtengo ~ 34.1 ciclos / clasificación (usando -O3), en comparación con la red de clasificación reordenada original obteniendo ~ 65.3 ciclos / clasificación (usando -O1, late -O2 y -O3).

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

Cambié, modifiqué el conjunto de pruebas para informar también los relojes por tipo y ejecuté más pruebas (la función cmp también se actualizó para manejar el desbordamiento de enteros), aquí están los resultados en algunas arquitecturas diferentes. Intenté probar en una CPU AMD pero rdtsc no es confiable en el X6 1100T que tengo disponible.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02

Me encontré con esta pregunta de Google hace unos días porque también tenía la necesidad de ordenar rápidamente una matriz de longitud fija de 6 enteros. Sin embargo, en mi caso, mis enteros son solo de 8 bits (en lugar de 32) y no tengo el requisito estricto de usar solo C. Pensé que compartiría mis hallazgos de todos modos, en caso de que puedan ser útiles para alguien ...

Implementé una variante de un tipo de red en el ensamblaje que usa SSE para vectorizar las operaciones de comparación e intercambio, en la medida de lo posible. Se necesitan seis "pases" para ordenar completamente la matriz. Utilicé un mecanismo novedoso para convertir directamente los resultados de PCMPGTB (comparación vectorizada) a parámetros aleatorios para PSHUFB (intercambio vectorizado), usando solo una instrucción PADDB (vectorized add) y en algunos casos también una instrucción PAND (bit a bit Y).

Este enfoque también tuvo el efecto secundario de producir una función verdaderamente sin ramas. No hay instrucciones de salto de ningún tipo.

Parece que esta implementación es aproximadamente un 38% más rápida que la implementación que actualmente está marcada como la opción más rápida en la pregunta ("Ordenar redes 12 con intercambio simple"). Modifiqué esa implementación para usar charelementos de matriz durante mis pruebas, para que la comparación sea justa.

Debo señalar que este enfoque se puede aplicar a cualquier tamaño de matriz de hasta 16 elementos. Espero que la ventaja de velocidad relativa sobre las alternativas crezca para las matrices más grandes.

El código está escrito en MASM para procesadores x86_64 con SSSE3. La función utiliza la "nueva" convención de llamadas de Windows x64. Aquí está...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

Puede compilar esto en un objeto ejecutable y vincularlo a su proyecto C. Para obtener instrucciones sobre cómo hacer esto en Visual Studio, puede leer este artículo . Puede usar el siguiente prototipo C para llamar a la función desde su código C:

void simd_sort_6(char *values);

El código de prueba es bastante malo; desborda la matriz inicial (¿no leen aquí las advertencias del compilador?), printf está imprimiendo los elementos incorrectos, usa .byte para rdtsc sin ninguna buena razón, solo hay una ejecución (!), no hay nada que verifique que el los resultados finales son realmente correctos (por lo que es muy fácil "optimizar" en algo sutilmente incorrecto), las pruebas incluidas son muy rudimentarias (¿no hay números negativos?) y no hay nada que impida que el compilador descarte toda la función como código muerto.

Dicho esto, también es bastante fácil mejorar la solución de red bitónica; simplemente cambie las cosas min / max / SWAP a

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

y sale aproximadamente un 65% más rápido para mí (Debian gcc 4.4.5 con -O2, amd64, Core i7).

Si bien me gusta la macro de intercambio proporcionada:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Veo una mejora (que un buen compilador podría hacer):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

Tomamos nota de cómo funcionan min y max y extraemos la sub-expresión común explícitamente. Esto elimina las macros mín. Y máx. Por completo.

Nunca optimice min / max sin benchmarking y mirando el ensamblaje generado por el compilador real. Si dejo que GCC optimice el mínimo con instrucciones de movimiento condicionales, obtengo un 33% de aceleración:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(280 vs. 420 ciclos en el código de prueba). Doing max with?: Es más o menos lo mismo, casi se pierde en el ruido, pero lo anterior es un poco más rápido. Este SWAP es más rápido con GCC y Clang.

Los compiladores también están haciendo un trabajo excepcional en la asignación de registros y el análisis de alias, moviendo efectivamente d [x] a las variables locales por adelantado y solo copiando de nuevo a la memoria al final. De hecho, lo hacen aún mejor que si trabajaras completamente con variables locales (como d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Escribo esto porque está asumiendo una fuerte optimización y, sin embargo, está intentando burlar al compilador en min / max. :)

Por cierto, probé Clang y GCC. Hacen la misma optimización, pero debido a las diferencias de programación, los dos tienen alguna variación en los resultados, no puedo decir cuál es más rápido o más lento. GCC es más rápido en las redes de clasificación, Clang en los tipos cuadráticos.

Solo para completar, también es posible el tipo de burbuja desenrollada y los tipos de inserción. Aquí está el tipo de burbuja:

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);

y aquí está el tipo de inserción:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

Este tipo de inserción es más rápido que el de Daniel Stutzbach, y es especialmente bueno en una GPU o una computadora con predicción porque ITER se puede hacer con solo 3 instrucciones (vs. 4 para SWAP). Por ejemplo, aquí está la t = d[2]; ITER(1); ITER(0);línea en el ensamblaje ARM:

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

Para seis elementos, la clasificación de inserción es competitiva con la red de clasificación (12 swaps vs. 15 iteraciones equilibra 4 instrucciones / intercambio vs. 3 instrucciones / iteración); tipo de burbuja, por supuesto, es más lento. Pero no será cierto cuando aumente el tamaño, ya que la ordenación por inserción es O (n ^ 2) mientras que las redes de ordenación son O (n log n).

Porté el conjunto de pruebas a una máquina de arquitectura PPC que no puedo identificar (no tuve que tocar el código, solo aumente las iteraciones de la prueba, use 8 casos de prueba para evitar resultados contaminantes con modificaciones y reemplace el rdtsc específico x86):

Llamada directa a la función de biblioteca qsort : 101

Implementación ingenua (tipo de inserción) : 299

Tipo de inserción (Daniel Stutzbach) : 108

Tipo de inserción desenrollado : 51

Redes de clasificación (Daniel Stutzbach) : 26

Redes de clasificación (Paul R) : 85

Clasificación de redes 12 con intercambio rápido : 117

Ordenar redes 12 Reordenado Intercambio : 116

Orden de rango : 56

Un intercambio XOR puede ser útil en sus funciones de intercambio.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

El if puede causar demasiada divergencia en su código, pero si tiene la garantía de que todos sus ints son únicos, esto podría ser útil.

Estoy ansioso por probar esto y aprender de estos ejemplos, pero primero algunos tiempos de mi Powerbook G4 PPC de 1.5 GHz con 1 GB de RAM DDR. (Tomé prestado un temporizador similar a rdtsc para PPC de http://www.mcs.anl.gov/~kazutomo/rdtsc.html para los horarios). Ejecuté el programa varias veces y los resultados absolutos variaron, pero el la prueba más rápida fue "Insertion Sort (Daniel Stutzbach)", con "Insertion Sort Unrolled" en segundo lugar.

Aquí está el último conjunto de veces:

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116

Aquí está mi contribución a este hilo: un shellsort optimizado de 1, 4 gap para un vector int (valp) de 6 miembros que contiene valores únicos.

void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

En mi computadora portátil HP dv7-3010so con un Athlon M300 de doble núcleo a 2 Ghz (memoria DDR2) se ejecuta en 165 ciclos de reloj. Este es un promedio calculado a partir del tiempo de cada secuencia única (6! / 720 en total). Compilado a Win32 usando OpenWatcom 1.8. El bucle es esencialmente un tipo de inserción y tiene 16 instrucciones / 37 bytes de longitud.

No tengo un entorno de 64 bits para compilar.

Si el tipo de inserción es razonablemente competitivo aquí, recomendaría probar un shellsort. Me temo que 6 elementos probablemente sean demasiado pequeños para estar entre los mejores, pero puede valer la pena intentarlo.

Código de ejemplo, sin probar, sin depurar, etc. Desea ajustar la secuencia inc = 4 e inc - = 3 para encontrar la secuencia óptima (pruebe inc = 2, inc - = 1, por ejemplo).

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

No creo que esto gane, pero si alguien publica una pregunta sobre cómo ordenar 10 elementos, quién sabe ...

Según Wikipedia, esto puede incluso combinarse con redes de clasificación: Pratt, V (1979). Shellsort y redes de clasificación (disertaciones sobresalientes en ciencias de la computación). Guirnalda. ISBN 0-824-04406-1

Sé que llego muy tarde, pero estaba interesado en experimentar con algunas soluciones diferentes. Primero, limpié esa pasta, la compilé y la puse en un repositorio. Mantuve algunas soluciones indeseables como callejones sin salida para que otros no lo intentaran. Entre esto estaba mi primera solución, que intentaba garantizar que x1> x2 se calculara una vez. Después de la optimización, no es más rápido que las otras versiones simples.

Agregué una versión en bucle del orden de clasificación, ya que mi propia aplicación de este estudio es para ordenar de 2 a 8 elementos, por lo que, dado que hay un número variable de argumentos, es necesario un bucle. Esta es también la razón por la que ignoré las soluciones de red de clasificación.

El código de prueba no probó que los duplicados se manejaran correctamente, por lo que si bien las soluciones existentes eran correctas, agregué un caso especial al código de prueba para garantizar que los duplicados se manejaran correctamente.

Luego, escribí un tipo de inserción que está completamente en los registros AVX. En mi máquina es un 25% más rápido que los otros tipos de inserción, pero un 100% más lento que el orden de clasificación. Lo hice solo para experimentar y no esperaba que fuera mejor debido a la ramificación en el tipo de inserción.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

Luego, escribí un orden de clasificación usando AVX. Esto coincide con la velocidad de las otras soluciones de orden de rango, pero no es más rápido. El problema aquí es que solo puedo calcular los índices con AVX, y luego tengo que hacer una tabla de índices. Esto se debe a que el cálculo se basa en el destino y no en la fuente. Consulte Conversión de índices basados ​​en origen a índices basados ​​en destino

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

El repositorio se puede encontrar aquí: https://github.com/eyepatchParrot/sort6/

Esta pregunta se está volviendo bastante antigua, pero en realidad tuve que resolver el mismo problema en estos días: agoritmos rápidos para ordenar pequeños arreglos. Pensé que sería una buena idea compartir mis conocimientos. Si bien comencé a usar redes de clasificación, finalmente logré encontrar otros algoritmos para los cuales el número total de comparaciones realizadas para clasificar cada permutación de 6 valores fue menor que con las redes de clasificación, y menor que con la clasificación de inserción. No conté el número de permutas; Esperaría que sea más o menos equivalente (tal vez un poco más alto a veces).

El algoritmo sort6usa el algoritmo sort4que usa el algoritmo sort3. Aquí está la implementación en alguna forma ligera de C ++ (el original tiene muchas plantillas para que pueda funcionar con cualquier iterador de acceso aleatorio y cualquier función de comparación adecuada).

Ordenar 3 valores

El siguiente algoritmo es un tipo de inserción desenrollado. Cuando se tienen que realizar dos swaps (6 asignaciones), en su lugar utiliza 4 asignaciones:

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

Parece un poco complejo porque el orden tiene más o menos una rama para cada permutación posible de la matriz, usando 2 ~ 3 comparaciones y como máximo 4 asignaciones para ordenar los tres valores.

Ordenar 4 valores

Éste llama sort3luego realiza una ordenación de inserción desenrollada con el último elemento de la matriz:

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

Este algoritmo realiza de 3 a 6 comparaciones y como máximo 5 intercambios. Es fácil desenrollar un tipo de inserción, pero usaremos otro algoritmo para el último tipo ...

Ordenar 6 valores

Este usa una versión desenrollada de lo que llamé un tipo de inserción doble . El nombre no es tan bueno, pero es bastante descriptivo, así es como funciona:

• Ordena todo menos el primer y el último elemento de la matriz.
• Cambie el primero y los elementos de la matriz si el primero es mayor que el último.
• Inserte el primer elemento en la secuencia ordenada desde el frente y luego el último elemento desde la parte posterior.

Después del intercambio, el primer elemento siempre es más pequeño que el último, lo que significa que, al insertarlos en la secuencia ordenada, no habrá más de N comparaciones para insertar los dos elementos en el peor de los casos: por ejemplo, si el el primer elemento ha sido insertado en la 3ra posición, luego el último no se puede insertar más abajo que la 4ta posición.

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

Mis pruebas en cada permutación de 6 valores muestran que este algoritmo siempre realiza entre 6 y 13 comparaciones. No calculé el número de intercambios realizados, pero no espero que sea superior a 11 en el peor de los casos.

Espero que esto ayude, incluso si esta pregunta ya no representa un problema real :)

EDITAR: después de ponerlo en el punto de referencia proporcionado, es claramente más lento que la mayoría de las alternativas interesantes. Tiende a funcionar un poco mejor que el tipo de inserción desenrollada, pero eso es todo. Básicamente, no es el mejor tipo para enteros, pero podría ser interesante para tipos con una operación de comparación costosa.

Creo que su pregunta tiene dos partes.

• El primero es determinar el algoritmo óptimo. Esto se hace, al menos en este caso, recorriendo cada pedido posible (no hay tantos) que le permite calcular la desviación mínima, máxima, promedio y estándar exacta de las comparaciones y los intercambios. Tenga un segundo puesto o dos a mano también.
• El segundo es optimizar el algoritmo. Se puede hacer mucho para convertir ejemplos de código de libros de texto en algoritmos reales y leves. Si se da cuenta de que un algoritmo no se puede optimizar en la medida requerida, intente un segundo puesto.

No me preocuparía demasiado por vaciar las tuberías (suponiendo x86 actual): la predicción de rama ha recorrido un largo camino. Lo que me preocupa es asegurarme de que el código y los datos quepan en una línea de caché cada uno (tal vez dos para el código). Una vez allí, las latencias de recuperación son refrescantemente bajas, lo que compensará cualquier pérdida. También significa que su bucle interno tendrá unas diez instrucciones o menos, que es justo donde debería estar (hay dos bucles internos diferentes en mi algoritmo de clasificación, son 10 instrucciones / 22 bytes y 9/22 de largo respectivamente). Suponiendo que el código no contiene ningún divs, puede estar seguro de que será cegadoramente rápido.

Sé que esta es una vieja pregunta.

Pero acabo de escribir un tipo diferente de solución que quiero compartir.
Usando nada más que MIN MAX anidado,

No es rápido, ya que usa 114 de cada uno,
podría reducirlo a 75 bastante simplemente así -> pastebin

Pero entonces ya no es puramente min max.

Lo que podría funcionar es hacer min / max en múltiples enteros a la vez con AVX

Referencia de PMINSW

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {1, 2, 3, 4, 5, 6},
    {6, 5, 4, 3, 2, 1},
    {100, 2, 300, 4, 500, 6},
    {100, 2, 3, 4, 500, 6},
    {1, 200, 3, 4, 5, 600},
    {1, 1, 2, 1, 2, 1}
  };

  unsigned long long cycles = rdtsc();
  for (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

EDITAR:
solución de orden de clasificación inspirada en Rex Kerr, mucho más rápido que el desastre anterior

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}

Descubrí que al menos en mi sistema, las funciones sort6_iterator()y las sort6_iterator_local()definidas a continuación se ejecutan al menos tan rápido, y con frecuencia notablemente más rápido, que el poseedor del récord actual anterior:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + y) = b; }

  SWAP(1, 2) SWAP(4, 5)
  SWAP(0, 2) SWAP(3, 5)
  SWAP(0, 1) SWAP(3, 4)
  SWAP(1, 4) SWAP(0, 3)
  SWAP(2, 5) SWAP(1, 3)
  SWAP(2, 4)
  SWAP(2, 3)
#undef SWAP
}

Pasé esta función de un std::vectoriterador en mi código de tiempo.

Sospecho (por comentarios como este y en otros lugares) que el uso de iteradores le da a g ++ ciertas garantías sobre lo que puede y no puede sucederle a la memoria a la que se refiere el iterador, que de lo contrario no tendría y son estas garantías las que permiten a g ++ optimice mejor el código de clasificación (por ejemplo, con punteros, el compilador no puede estar seguro de que todos los punteros apuntan a diferentes ubicaciones de memoria). Si recuerdo correctamente, esto también es parte de la razón por la cual tantos algoritmos STL, como std::sort(), generalmente tienen un rendimiento tan obsceno.

Por otra parte, sort6_iterator()es algunas veces (de nuevo, dependiendo del contexto en el que se llama a la función) superado constantemente por la siguiente función de clasificación, que copia los datos en variables locales antes de la clasificación ellos. ¹ Tenga en cuenta que dado que solo hay 6 variables locales definidas, si estas variables locales son primitivas, es probable que nunca se almacenen en la RAM y que solo se almacenen en los registros de la CPU hasta el final de la llamada a la función, lo que ayuda a hacer esta clasificación Funcionan rápido. (También ayuda que el compilador sepa que distintas variables locales tienen ubicaciones distintas en la memoria).

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

Tenga en cuenta que la definición de la SWAP()siguiente manera algunas veces resulta en un rendimiento ligeramente mejor, aunque la mayoría de las veces resulta en un rendimiento ligeramente peor o una diferencia insignificante en el rendimiento.

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

Si solo desea un algoritmo de ordenación que en los tipos de datos primitivos, gcc -O3 sea consistentemente bueno para la optimización, sin importar en qué contexto aparezca la llamada a la función de ordenación en ¹ , luego, dependiendo de cómo pase la entrada, intente uno de los dos siguientes algoritmos:

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

O si desea pasar las variables por referencia, use esto (la función a continuación difiere de la anterior en sus primeras 5 líneas):

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

La razón para usar la registerpalabra clave es porque esta es una de las pocas veces que sabe que desea estos valores en los registros. Sin register, el compilador resolverá esto la mayor parte del tiempo, pero a veces no lo hace. El uso de la registerpalabra clave ayuda a resolver este problema. Sin embargo, normalmente no use la registerpalabra clave ya que es más probable que ralentice su código que lo acelere.

Además, tenga en cuenta el uso de plantillas. Esto se hace a propósito ya que, incluso con la inlinepalabra clave, las funciones de plantilla generalmente están mucho más agresivamente optimizadas por gcc que las funciones vanilla C (esto tiene que ver con gcc que necesita tratar con punteros de función para funciones vanilla C pero no con funciones de plantilla).

1. Mientras cronometraba varias funciones de clasificación, noté que el contexto (es decir, el código circundante) en el que se realizó la llamada a la función de clasificación tuvo un impacto significativo en el rendimiento, lo que probablemente se deba a que la función está en línea y luego optimizada. Por ejemplo, si el programa era lo suficientemente simple, generalmente no había mucha diferencia en el rendimiento entre pasar la función de clasificación a un puntero versus pasarle un iterador; de lo contrario, el uso de iteradores generalmente resultó en un rendimiento notablemente mejor y nunca (en mi experiencia hasta ahora al menos) un rendimiento notablemente peor. Sospecho que esto puede deberse a que g ++ puede optimizar globalmente un código suficientemente simple.

Intente "fusionar la lista ordenada". :) Use dos arreglos. Más rápido para pequeñas y grandes series.
Si concatena, solo verifica dónde se inserta. Otros valores más grandes que no necesita comparar (cmp = ab> 0).
Para 4 números, puede usar el sistema 4-5 cmp (~ 4.6) o 3-6 cmp (~ 4.9). El tipo de burbuja utiliza 6 cmp (6). Un montón de cmp para grandes números de código más lento.
Este código usa 5 cmp (no ordena MSL):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}

Principial MSL 9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8

código js

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Ordenar 4 elementos con uso cmp == 0. Los números de cmp son ~ 4.34 (los nativos de FF tienen ~ 4.52), pero tardan 3 veces más que fusionar listas. Pero mejor menos operaciones cmp, si tiene números grandes o texto grande. Editar: error reparado

Prueba en línea http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}

Tal vez yo soy tarde a la fiesta, pero al menos mi aportación es un nuevo enfoque.

• El código realmente debería estar en línea
• incluso si está en línea, hay demasiadas ramas
• la parte de análisis es básicamente O (N (N-1)) que parece estar bien para N = 6
• el código podría ser más efectivo si el costoswap fuera más alto (es decir, el costo de compare)
• Confío en que las funciones estáticas estén en línea.
• El método está relacionado con la clasificación de clasificación
  • en lugar de rangos, se usan los rangos relativos (compensaciones).
  • la suma de los rangos es cero para cada ciclo en cualquier grupo de permutación.
  • en lugar de SWAP()dos elementos, los ciclos se persiguen, necesitando solo una temperatura y un intercambio (registro-> registro) (nuevo <- antiguo).

Actualización: cambió un poco el código, algunas personas usan compiladores C ++ para compilar código C ...

#include <stdio.h>

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}

//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

    wire( 0, 1); wire( 2, 3); wire( 4, 5);
    wire( 3, 5); wire( 0, 2); wire( 1, 4);
    wire( 4, 5); wire( 2, 3); wire( 0, 1); 
    wire( 3, 4); wire( 1, 2); 
    wire( 2, 3);

    #undef wire
}

Bueno, si son solo 6 elementos y puede aprovechar el paralelismo, quiere minimizar la ramificación condicional, etc. ¿Por qué no genera todas las combinaciones y prueba el orden? Me atrevería a decir que en algunas arquitecturas, puede ser bastante rápido (siempre que tenga la memoria preasignada)

Aquí hay tres métodos de clasificación típicos que representan tres clases diferentes de Algoritmos de clasificación:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

¿Pero mira la discusión de Stefan Nelsson sobre el algoritmo de clasificación más rápido? donde discute una solución que se reduce a O(n log log n)... verifique su implementación en C

Este algoritmo de clasificación semi-lineal fue presentado por un artículo en 1995:

A. Andersson, T. Hagerup, S. Nilsson y R. Raman. ¿Clasificación en tiempo lineal? En Actas del 27º Simposio anual de ACM sobre la teoría de la informática, páginas 427-436, 1995.