Oto implementacja wykorzystująca sortowanie sieci :

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);  
}

Naprawdę potrzebujesz do tego bardzo wydajnych implementacji bezgałęziowych min i max, ponieważ do tego właśnie sprowadza się ten kod-sekwencja operacji min i max (łącznie po 13). Zostawiam to jako ćwiczenie dla czytelnika.

Zauważ, że ta implementacja łatwo nadaje się do wektoryzacji (np. SIMD-większość Isa SIMD ma wektorowe instrukcje min / max), a także do GPU implementacje (np. CUDA - bez rozgałęzień nie ma problemów z rozbieżnością warp itp.).

Zobacz także: szybka implementacja algorytmu do sortowania bardzo małej listy

Ponieważ są to liczby całkowite i porównania są szybkie, dlaczego nie obliczyć kolejności Rang każdego bezpośrednio:

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];
}

Wygląda na to, że spóźniłem się na imprezę rok później, ale zaczynamy...

Patrząc na assembly wygenerowane przez gcc 4.5.2 zauważyłem, że ładunki i zapasy są wykonywane dla każdego swapu, co naprawdę nie jest potrzebne. Lepiej byłoby załadować 6 wartości do rejestrów, posortować je i zapisać z powrotem do pamięci. Zamówiłem ładunki w sklepach, aby były jak najbliżej tam, rejestry są najpierw potrzebne i ostatnio używane. Użyłem też makra Swap Steinara H. Gundersona. Update: przełączyłem się na Makro SWAP Paolo Bonziniego, które GCC konwertuje na coś podobnego do Gundersona, ale gcc jest w stanie lepiej uporządkować instrukcje, ponieważ nie są one podane jako explicit assembly.

Użyłem tej samej kolejności swapów, co reordered swap network, biorąc pod uwagę najlepsze wyniki, chociaż może być lepsze zamówienie. Jeśli znajdę więcej czasu, wygeneruję i przetestuję kilka permutacji.

Zmieniłem kod testowy, aby uwzględnić ponad 4000 tablic i pokazać średnią liczbę cykli musiałem posortować każdą. Na i5-650 dostaję ~34.1 cykli/sort (używając-O3), w porównaniu do oryginalnej sieci sortującej zmieniającej kolejność otrzymuję ~65.3 cykli/sort (używając-o1, beats-O2 i-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;
}

Zmieniłem zmodyfikowałem zestaw testów , aby raportować Zegary według sortowania i uruchamiać więcej testów( funkcja cmp została zaktualizowana do obsługi przepełnienia liczb całkowitych), oto wyniki na niektórych różnych architekturach. Próbowałem testować na procesorze AMD, ale rdtsc nie jest wiarygodne na X6 1100T mam dostępny.

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

Kod testowy jest dość zły; przepełnia początkową tablicę (czy ludzie tutaj nie czytają ostrzeżeń kompilatora?), printf drukuje niewłaściwe elementy, używabajt dla rdtsc bez powodu, jest tylko jeden run (!), nie ma nic sprawdzającego, czy wyniki końcowe są rzeczywiście poprawne (więc bardzo łatwo jest "zoptymalizować" w coś subtelnie błędnego), zawarte testy są bardzo podstawowe (brak liczb ujemnych?) i nic nie powstrzyma kompilatora przed odrzuceniem całego funkcja jako martwy kod.

To powiedziawszy, jest również dość łatwe do ulepszenia w rozwiązaniu sieci bitonicznej; po prostu zmień min / max / SWAP na

#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"); }

I wychodzi mi o 65% szybciej (Debian GCC 4.4.5 z -O2, amd64, Core i7).

Natknąłem się na to pytanie z Google kilka dni temu, ponieważ miałem również potrzebę szybkiego sortowania tablicy o stałej długości 6 liczb całkowitych. W moim przypadku jednak moje liczby całkowite to tylko 8 bitów (zamiast 32) i nie mam ścisłego wymogu używania tylko C. pomyślałem, że i tak podzielę się moimi odkryciami, na wypadek, gdyby mogły być komuś pomocne...

Zaimplementowałem wariant sortowania sieci w assembly, który używa SSE do wektoryzowania operacji compare i swap, w zakresie możliwe. Potrzeba sześciu "przejść", aby całkowicie posortować tablicę. Użyłem nowatorskiego mechanizmu do bezpośredniej konwersji wyników PCMPGTB (wektoryzowane porównanie) na parametry shuffle dla PSHUFB (wektoryzowane swap), używając tylko PADDB (wektoryzowane dodanie), a w niektórych przypadkach także instrukcji PAND (bitowe and).

Wygląda na to, że ta implementacja jest o 38% szybsza niż implementacja, która jest obecnie oznaczana jako najszybsza opcja w pytaniu ("Sorting Networks 12 with Simple Swap"). Zmodyfikowałem tę implementację, aby używać char elementów tablicy podczas moich testów, aby porównanie było sprawiedliwe.

Należy zauważyć, że to podejście może być stosowane do dowolnej wielkości tablicy do 16 elementów. Spodziewam się względnej przewagi prędkości nad alternatywami, aby powiększyć się dla większych tablic.

Kod jest napisany w MASM dla procesory x86_64 z SSSE3. Funkcja używa "nowej" konwencji wywołania systemu Windows x64. Tutaj jest...

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

Możesz skompilować to do obiektu wykonywalnego i połączyć go ze swoim projektem C. Aby dowiedzieć się, jak to zrobić w Visual Studio, możesz przeczytać ten artykuł . Możesz użyć następującego prototypu C do wywołania funkcji z kodu C:

void simd_sort_6(char *values);

Podczas gdy bardzo podoba mi się Makro swap:

#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; }

Widzę poprawę (co może zrobić dobry kompilator):

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

Zwracamy uwagę na to, jak działają min i max i wyciągamy jawnie wspólne wyrażenie podrzędne. To całkowicie eliminuje makra min i max.

Nigdy nie Optymalizuj min/max bez benchmarkingu i patrzenia na rzeczywisty kompilator wygenerowany assembly. Jeśli pozwolę GCC zoptymalizować min z warunkowymi instrukcjami ruchu, dostaję 33% speedup:

#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 cykli w kodzie testowym). Z Maxem ?: jest mniej więcej taki sam, prawie zagubiony w hałasie, ale powyższy jest trochę szybszy. Ta wymiana jest szybsza zarówno z GCC, jak i Clang.

Kompilatory wykonują również wyjątkową pracę przy alokacji rejestrów i analizie aliasów, efektywnie przenosząc d [x] do zmiennych lokalnych z góry i kopiując z powrotem do pamięci dopiero na końcu. W rzeczywistości robią to nawet lepiej, niż gdybyś pracował całkowicie z lokalnymi zmiennymi (jak d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). Piszę to, ponieważ zakładasz silną optymalizację, a mimo to próbujesz przechytrzyć kompilator na min / max. :)

Tylko dla kompletności, rozwijane sortowanie bąbelków i sortowanie wstawiania są również możliwe. Oto Sortuj bańki:

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);

A oto sortowanie wstawiania:

//#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);

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

Dla sześciu elementów sortowanie wstawiania jest konkurencyjne z siecią sortującą (12 swapów vs. 15 iteracji równoważy 4 instrukcje / swap vs. 3 Instrukcje/ iteracja); oczywiście bubble sort jest wolniejszy. Ale to nie będzie prawda, gdy rozmiar rośnie, ponieważ wstawianie sortowania jest O (N^2) podczas sortowania sieci są O (n log n).

Przeportowałem zestaw testów na maszynę z architekturą PPC, której nie mogę zidentyfikować (nie musiałem dotykać kodu, tylko zwiększyć iteracje testu, użyć przypadków testowych 8, aby uniknąć zanieczyszczania wyników za pomocą modów i zastąpić specyficzne dla x86 rdtsc): {]}

Bezpośrednie wywołanie funkcji biblioteki qsort : 101

Naiwna implementacja (wstawianie) : 299

Wstawianie (Daniel Stutzbach) : 108

Wstawianie Sortowania Rozwiniętego : 51

Sortowanie Sieci (Daniel Stutzbach) : 26

Sortowanie Sieci (Paul R) : 85

Sortowanie sieci 12 z szybką wymianą : 117

Sortowanie sieci 12 : 116

Kolejność Stopni : 56

Wymiana XOR może być przydatna w funkcjach wymiany.

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

If może powodować zbyt duże rozbieżności w kodzie, ale jeśli masz gwarancję, że wszystkie Twoje ints są unikalne, może to być przydatne.

Nie mogę się doczekać, aby spróbować swoich sił w tym i uczyć się na tych przykładach, ale najpierw kilka timingów z mojego PowerBooka G4 1.5 GHz PPC w / 1 GB DDR RAM. (Pożyczyłem podobny timer rdtsc do PPC z http://www.mcs.anl.gov / ~kazutomo/rdtsc.html na czas.) Uruchomiłem program kilka razy i absolutne wyniki różniły się, ale konsekwentnie najszybszym testem było " Wstawianie sortowania (Daniel Stutzbach)", z "Wstawianie sortowania rozwinięty" blisko sekundy.

Oto ostatni zestaw czas:

**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

Oto mój wkład do tego wątku: zoptymalizowany 1, 4 Gap shellsort dla 6-członowego wektora int (valp) zawierającego unikalne wartości.

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);
}

Nie mam 64-bitowe środowisko do kompilacji.

Jeśli sortowanie wstawiania jest tutaj dość konkurencyjne, polecam wypróbowanie shellsort. Obawiam się, że 6 elements to chyba za mało, aby było wśród najlepszych, ale może warto spróbować.

Przykładowy kod, untested, undebugged, etc. Chcesz dostroić sekwencję inc = 4 I inc -= 3, aby znaleźć optymalną (spróbuj na przykład inc = 2, inc -= 1).

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;
        }
    }
}

Myślę, że to nie wygra, ale jeśli ktoś posty pytanie o sortowanie 10 elementów, kto wie...

Według Wikipedii można to nawet łączyć z sieciami sortującymi: Pratt, V (1979). Shellsort and sorting networks (wybitne prace doktorskie w dziedzinie informatyki). Garland. ISBN 0-824-04406-1

To pytanie staje się dość stare, ale w rzeczywistości musiałem rozwiązać ten sam problem w dzisiejszych czasach: szybkie agorytmy do sortowania małych tablic. Pomyślałem, że dobrze byłoby podzielić się moją wiedzą. Podczas gdy po raz pierwszy zacząłem używać sortowania sieci, w końcu udało mi się znaleźć inne algorytmy, dla których całkowita liczba porównań wykonanych do sortowania każdej permutacji 6 wartości była mniejsza niż w przypadku sortowania sieci i mniejsza niż w przypadku sortowania wstawiania. Nie liczyłem ilości swapów; d spodziewaj się, że będzie mniej więcej równoważna(może czasami trochę wyższa).

Algorytm sort6 wykorzystuje algorytm sort4, który wykorzystuje algorytm sort3. Oto implementacja w nieco lekkiej formie C++ (oryginał jest ciężki w szablonach, więc może pracować z dowolnym iteratorem o dostępie losowym i dowolną odpowiednią funkcją porównawczą).

Sortowanie 3 wartości

Poniższy algorytm jest rodzajem wstawiania nierolowanego. Gdy trzeba wykonać dwa swapy (6 zadań), wykorzystuje się 4 zadania zamiast:

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]);
            }
        }
    }
}

Wygląda to na nieco skomplikowane, ponieważ sortowanie ma mniej więcej jedną gałąź dla każdej możliwej permutacji tablicy, używając 2~3 porównań i maksymalnie 4 przydziałów do sortowania trzech wartości.

Sortowanie 4 wartości

Ten wywołuje sort3, a następnie wykonuje nierozwinięty sortowanie wstawiania z ostatnim elementem tablicy:

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]);
            }
        }
    }
}

Algorytm ten wykonuje od 3 do 6 porównań i co najwyżej 5 swapów. Łatwo jest rozwinąć rodzaj wstawiania, ale będziemy użyj innego algorytmu do ostatniego sortowania...

Sortowanie 6 wartości

Ten używa rozwiniętej wersji tego, co nazwałem sortowaniem podwójnego wstawiania . Nazwa nie jest zbyt wielka, ale jest dość opisowa, oto jak to działa: {]}

• sortuje wszystko oprócz pierwszego i ostatniego elementu tablicy.
• Zamień pierwszy i elementy tablicy, jeśli pierwszy jest większy od ostatniego.
• Wstaw pierwszy element do posortowanej sekwencji z przodu ostatni element z tyłu.

Po swapie pierwszy element jest zawsze mniejszy od ostatniego, co oznacza, że podczas wstawiania go do sortowanej sekwencji nie będzie więcej niż N porównań, aby wstawić dwa elementy w najgorszym przypadku: na przykład, jeśli pierwszy element został wstawiony na 3.pozycji, to ostatni nie może być wstawiony poniżej 4. pozycji.

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]);
                }
            }
        }
    }
}

Moje testy każdej permutacji 6 wartości pokazują, że algorytmy te zawsze wykonują między 6 a 13 porównań. Nie obliczyłem liczby wykonanych swapów, ale nie spodziewam się, że w najgorszym przypadku będzie ona wyższa niż 11.

Mam nadzieję, że to pomoże, nawet jeśli to pytanie może już nie stanowić faktycznego problemu:)

EDIT: Po umieszczeniu go w podanym benchmarku, jest wolniejszy niż większość ciekawych alternatyw. Wydaje się, że działa nieco lepiej niż rozwijany rodzaj wstawiania, ale jest to dość dużo. Zasadniczo nie jest to najlepszy rodzaj dla liczb całkowitych, ale może być interesujący dla typów z kosztowną operacją porównywania.

Wiem, że jestem bardzo spóźniony, ale byłem zainteresowany eksperymentowaniem z różnymi rozwiązaniami. Najpierw wyczyściłem tę pastę, skompilowałem ją i umieściłem w repozytorium. Trzymałem pewne niepożądane rozwiązania jako ślepe zaułki, aby inni nie próbowali. Wśród nich było moje pierwsze rozwiązanie, które próbowało zapewnić, że x1>x2 został obliczony raz. Po optymalizacji nie jest szybszy od innych, prostych wersji.

Dodałem zapętloną wersję sortowania kolejności Rang, ponieważ mój własny zastosowanie tego badania jest do sortowania 2-8 pozycji, więc ponieważ istnieje zmienna liczba argumentów, konieczna jest pętla. Dlatego też zignorowałem rozwiązania sieci sortowania.

Kod testowy nie sprawdzał, czy duplikaty były obsługiwane poprawnie, więc chociaż istniejące rozwiązania były poprawne, dodałem specjalny przypadek do kodu testowego, aby upewnić się, że duplikaty były obsługiwane poprawnie.

Potem napisałem rodzaj wstawiania, który jest w całości w rejestrach AVX. Na mojej maszynie jest 25% szybciej niż inne rodzaje wstawiania, ale 100% wolniej niż kolejność Rang. Zrobiłem to wyłącznie dla eksperymentu i nie spodziewałem się, że będzie to lepsze ze względu na rozgałęzienia w rodzaju wstawiania.

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
}

Następnie napisałem sortowanie kolejności Rang przy użyciu AVX. Odpowiada to szybkości innych rozwiązań rzędu Rang, ale nie jest szybsze. Problem polega na tym, że mogę obliczyć indeksy tylko za pomocą AVX, a następnie muszę sporządzić tabelę indeksów. Dzieje się tak, ponieważ obliczenia są oparte na miejscu przeznaczenia raczej niż na podstawie źródła. Zobacz Konwersja z indeksów źródłowych do indeksów docelowych

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];
}

Repo można znaleźć tutaj: https://github.com/eyepatchParrot/sort6/

Uważam, że są dwie części twojego pytania.

• pierwszy polega na określeniu algorytmu optymalnego. Odbywa się to - przynajmniej w tym przypadku - poprzez zapętlenie każdego możliwego zamówienia (nie ma ich zbyt wielu), co pozwala obliczyć dokładne min, max, średnie i standardowe odchylenie porównań i swapów. Miej też pod ręką drugie miejsce lub dwa.
• drugim jest optymalizacja algorytmu. Wiele można zrobić, aby konwertować podręcznikowe przykłady kodu na średnie i szczupłe algorytmy. Jeśli zdajesz sobie sprawę, że algorytm nie może być zoptymalizowany w wymaganym zakresie, spróbuj runner-up.

Nie martwiłbym się zbytnio o opróżnianie rurociągów (zakładając obecne x86): przewidywanie gałęzi przebyło długą drogę. To, o co bym się martwił, to upewnienie się, że kod i dane mieszczą się w jednej linii pamięci podręcznej (może dwie dla kodu). Po pobraniu opóźnienia są odświeżająco niskie, co zrekompensuje każde opóźnienie. Oznacza to również, że twoja wewnętrzna pętla będzie może dziesięć instrukcje lub tak, która jest dokładnie tam, gdzie powinna być (istnieją dwie różne wewnętrzne pętle w moim algorytmie sortowania, są one odpowiednio 10 instrukcji/22 bajty i 9/22 długości). Zakładając, że kod nie zawiera żadnych divów, możesz być pewien, że będzie ślepo szybki.

Odkryłem, że przynajmniej w moim systemie funkcje sort6_iterator() i sort6_iterator_local() zdefiniowane poniżej działały co najmniej tak szybko, a często zauważalnie szybciej, niż powyższy aktualny rekordzista:

#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
}

Przekazałem tę funkcję iterator std::vector w moim kodzie czasowym. Podejrzewam, że używanie iteratorów daje g++ pewne zapewnienia o tym, co może, a czego nie może się stać z pamięcią, do której odnosi się iterator, czego w przeciwnym razie nie miałby i to właśnie te zapewnienia pozwalają g++ lepiej zoptymalizować kod sortujący (który, o ile dobrze pamiętam, jest również częścią powodu, dla którego tak wiele algorytmów std, takich jak std::sort(), generalnie ma tak nieprzyzwoicie dobrą wydajność). Jednak podczas timing zauważyłem, że kontekst (tj. otaczający kod), w którym wywołanie funkcji sortowania zostało wykonane, miał znaczący wpływ na wydajność, co prawdopodobnie wynika z funkcji inlined, a następnie zoptymalizowany. Na przykład, jeśli program był wystarczająco prosty, to zwykle nie było duża różnica w wydajności między przekazaniem funkcji sortowania wskaźnika a przekazaniem iteratora; w przeciwnym razie używanie iteratorów Zwykle skutkowało zauważalnie lepszą wydajnością i nigdy (przynajmniej z mojego doświadczenia) zauważalnie gorszą wydajnością. Podejrzewam, że może to być dlatego, że g++ może globalnie zoptymalizować wystarczająco prosty kod.

Ponadto, sort6_iterator()jest niektóre razy (ponownie, w zależności od kontekstu, w którym funkcja jest wywoływana) konsekwentnie wyróżnia się następującą funkcję sortowania:

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
}

Zauważ, że zdefiniowanie {[11] } w następujący sposób niektóre razy skutkuje nieco lepszą wydajnością, chociaż w większości przypadków skutkuje nieco gorszą wydajnością lub znikomą różnicą w wydajności.

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

Jeśli chcesz tylko algorytm sortowania, który gcc-O3 jest konsekwentnie dobry w optymalizacji, to w zależności od tego, jak przekazujesz dane wejściowe, spróbuj jednego z następujących dwóch algorytmy:

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
}

Lub

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
}

Powodem użycia słowa kluczowego register jest to, że jest to jeden z niewielu przypadków, kiedy wiesz, że chcesz te wartości w rejestrach. Bez register kompilator domyśli się tego przez większość czasu, ale czasami tak nie jest. użycie słowa kluczowego register pomaga rozwiązać ten problem. Zwykle jednak nie używaj słowa kluczowego register, ponieważ jest to bardziej prawdopodobne, aby spowolnić Kod niż przyspieszyć go.

Zwróć również uwagę na użycie szablonów. Zrobione. celowo ponieważ, nawet ze słowem kluczowym inline, funkcje szablonu są na ogół znacznie bardziej agresywnie zoptymalizowane przez gcc niż funkcje vanilla C (ma to związek z gcc potrzebującym radzenia sobie ze wskaźnikami funkcji dla funkcji vanilla C, ale nie z funkcjami szablonu).

Wiem, że to stare pytanie.

Ale właśnie napisałem inny rodzaj rozwiązania, którym chcę się podzielić.
Użycie tylko zagnieżdżonego MIN MAX,

Nie jest szybki, ponieważ zużywa 114 z każdego,
może zredukować do 75 całkiem po prostu tak - > pastebin

Co może działać, robi min / max na wielu liczbach całkowitych jednocześnie z AVX

Pminsw reference

#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]);
  }
}

EDIT:
Ranga rozwiązanie zamówienia inspirowane Rexem Kerrem, Dużo szybciej niż powyżej

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;
}

Spróbuj sortować' scalanie posortowanej listy'. :) Użyj dwóch tablic. Najszybszy dla małych i dużych tablic.
Jeśli chcesz, sprawdź tylko gdzie wstawić. Inne większe wartości, których nie trzeba porównywać (cmp = a-b>0).
Dla 4 liczb można użyć systemu 4-5 cmp (~4,6) lub 3-6 CMP (~4,9). Sortuj bańki użyj 6 cmp (6). Dużo cmp dla dużych liczb wolniejszy kod.
Ten kod używa 5 CMP (nie MSL sort):
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

Kod 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;
	}
}

Sortuj 4 pozycje z użyciem cmp= = 0. Liczba cmp wynosi ~4.34 (natywne FF mają ~4.52), ale zajmuje 3x czasu niż listy scalające. Ale lepiej mniej operacji cmp, jeśli masz duże liczby lub duży tekst. Edit: Naprawiono błąd

Test Online 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;
}

Może ijestem spóźniony na imprezę, ale przynajmniej mój wkład to nowe podejście.

• Kod naprawdę powinien być inlined
• nawet jeśli inlined, istnieje zbyt wiele gałęzi
• część analizująca jest w zasadzie O (N (N-1)), co wydaje się OK dla N=6
• Kod może być bardziej skuteczny, jeśli koszt swap byłoby wyższe (irt koszt compare)
• ufam, że funkcje statyczne są wbudowane.
• metoda jest powiązane z rank-sort
  • zamiast Rang używane są względne rangi (offsety).
  • suma szeregów jest równa zero dla każdego cyklu W dowolnej grupie permutacji.
  • zamiast SWAP() dwóch elementów, cykle są ścigane, potrzebując tylko jednej temp i jednej (register->register) swap (new

Update: zmieniono nieco kod, niektórzy używają kompilatorów C++ do kompilowania kodu 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);
}

Cóż, jeśli jest to tylko 6 elementów i możesz wykorzystać równoległość, chcesz zminimalizować rozgałęzienia warunkowe itp. Dlaczego nie generujesz wszystkich kombinacji i nie testujesz na zamówienie? Zaryzykowałbym, że w niektórych architekturach może to być dość szybkie (o ile masz wstępnie przydzieloną pamięć)

Oto trzy typowe metody sortowania reprezentujące trzy różne klasy algorytmów sortowania:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

Ale zobacz Stefan Nelsson dyskusja na temat najszybszego algorytmu sortowania? gdzie omawia rozwiązanie, które sprowadza się do O(n log log n) .. sprawdź jego implementację w C

Ten półliniowy algorytm sortowania został przedstawiony w pracy w 1995 roku:

A. Andersson, T. Hagerup, S. Nilsson i R. Raman. / Align = "left" / linear czas? W Postępowaniu z 27. dorocznego sympozjum ACM na temat teorii Computing, pages 427-436, 1995.