Hissort
is a novelty sorting algorithm which is in average 2 - 3 times faster than fastest* QuickSort algorithm, used in C++ std::sort.
hissort(buffer.begin(), buffer.end());
hissort(buffer.begin(), buffer.end(), false);
hissort(buffer.begin(), buffer.end(), std::less<>{});
hissort(buffer.begin(), buffer.end(), std::greater<>{});
hissort(buffer.rbegin(), buffer.rend(), std::greater<>{});
hissort(rawBuffer_ptr, rawBuffer_ptr + buffSize, std::less<>{});
G{8{h-{ ;h\{< T{u2 .V2 .g.I
Rr \r -{{ \a{ \{-\ o{-c8\-< 4r`[ho)-rj 4aho\- Da{ -rcou{ ur;{- a)--ro\s*2*2M)[< Tr?j8rh;
Tr?j8rh;- ho{ ucoo{j\8( cjhEh)8hK8{ K{uhc-{ \a{ h80ro)\a` )- )j [{{oso{E){? [oru{-- K{/ro{ [cK8)uh\)rj2 Da{ {j; r/ \a{ o{E){? ?)88 K{ hjjrcju{; rj \a)- ?{K [h0{2 o{h; `ro{222
Da{ h80ro)\a` ah- \a{ /r88r?)j0 \oh)\-<
1 Ac)u6!ro\ h- \a{ /h-\{-\ -ro\)j0 h80ro)\a` )- [cK8)u8( {`Kohu{; urj-{j-c-, h8\arc0a \a{o{ ho{ r\a{o r[)j)rj-2
11 R{j{oh\)E{ h262h2 qjr\s-\hK8{q )j \a{ -ro\)j0 \{o`)jr8r0( `{hj- )\ uhjjr\ 0hcohj\{{ ro;{o r/ \a{ -h`{ Eh8c{- /or` \a{ ro)0)jh8 Kc//{o2 La)8{ \a{ `r-\ r/ \)`{ )\ 6{{[- ro)0)jh8 ro;{o r/ \a{ -h`{ Eh8c{-, \a{o{ ho{ [ho\- r/ \a{ h80ro)\a` \ah\ uhj q0{j{oh\{q Eh8c{- )j-\{h; r/ ur[()j0 \a{`2
Da{ -h`{ r[\)`)Mh\)rj h[[orhua )- c-{; )j \a{ 4## !DW std::sort /cju\)rj s h a(Ko); 5j\or!ro\ h80ro)\a`, ?a)ua c-{- \a{ Ac)u6!ro\, F{h[!ro\, Kc\ /ro -`h88 )j\{oEh8 -)M{-, )\ -?)\ua{- \r \a{ 5j-{o\)rj!ro\2
5\ )- )`[ro\hj\ \r 6jr? \a{ ;)-\)u\)rj K{\?{{j [co{ Ac)u6!ro\ hj; std::sort, hj; -)`)8ho8(, K{\?{{j [co{ a)--ro\ hj; r[\)`)M{; a)--ro\2 Da{o{/ro{ \r K{ /h)o, rj8( \a{ r[\)`)M{; a)--ro\ -arc8; K{ ur`[ho{; \r \a{ std::sort, ro \r -)`)8ho r[\)`)M{; a(Ko); h80ro)\a`-2 Da{ r[\)`)M{; a)--ro\ ?h- c-{; )j \a{ ur`[ho)-rj \{-\- K{8r?, hj; \a{ r[\)`)M{; E{o-)rj ah- h8-r K{{j )juro[roh\{; )j\r \a{ r//)u)h8 -rcou{ ur;{ o{8{h-{2
Hro \a{ -`h88{-\ -)M{- K{8r? I, a)--ro\ nc-\ -?h[- \a{ Eh8c{- c-)j0 )/s{8-{ K8ru6-2
111 }{uhc-{ C. )- \a{ hj-?{o \r \a{ c8\)`h\{ 'c{-\)rj r/ 8)/{, \a{ cj)E{o-{, hj; {E{o(\a)j0222
/r88r?)j0 `h|)`c` o{uco-)rj ;{[\a-<
Da{ o{h-rj )- rKE)rc-<
4f4## )- 8r?s8{E{8 yhj; h8-r a)0as8{E{8i ?);{s-[o{h; /8{|)K8{ 8hj0ch0{ r[\)`)M{; /ro -[{{;2 vE{o( -uo)[\ ro ocj\)`{sKh-{; [or0oh``)j0 8hj0ch0{ y{202 7hEh, 7hEh!uo)[\, 4+, ^F^, ^(\arj, D([{!uo)[\, {\u2i, ahE{ )\- r?j )j\{o[o{\{o ro ocj\)`{ uro{ ?o)\\{j )j h 8r?s8{E{8 8hj0ch0{, c-c-h88( )j 4f4## yro {E{j )j \a{ 4^_ h--{`K8(i2 vE{o( ?{K Kor?-{o, ;h\hKh-{ {j0)j{, ro hj( -[{{;s\a)o-\( h[[8)uh\)rj )`[8{`{j\- )\- -[{{; uo)\)uh8 [ho\- )j \a{ 8r?s8{E{8 8hj0ch0{2
5/ (rc j{{; \r ahE{ )`[8{`{j\{; a)--ro\ h80ro)\a` )j h [or0oh``)j0 8hj0ch0{ r/ (rco uar)u{, \a{j h-6 ;{E{8r[{o- r/ \a{ 8hj0ch0{ \r r//)u)h88( )juro[roh\{ )\ h- h 8)Koho( /cju\)rj \r hua){E{ `h|)`c` -[{{;2 Fr?{E{o, -cua h -\{[ ?rc8; o{'c)o{ [{o`)--)rj /or` \a{ h80ro)\a` r?j{o2 Lo)\)j0 \a)- h80ro)\a` )j hj )j\{o[o{\{; 8hj0ch0{ )\-{8/ ;r{-jq\ `h6{ hj( -{j-{, )\ ?)88 o{-c8\ )j [{o/ro`hu{ -8r?{o \ahj \a{ 8hj0ch0{q- h8o{h;( hEh)8hK8{ -ro\)j0 /cju\)rj-2
Da{ /r88r?)j0 R44 ur`[)8{o ur``hj; uo{h\{- libhissort.a W)jc| -\h\)u 8)Koho(<
H)jh88(, \a{ libhissort.a 8)Koho( uhj K{ 8)j6{; ?)\a \a{ usage.c <
hj; ur`[)8{; )j\r hissortest {|{uc\hK8{ ?)\a \a{ /r88r?)j0 ur``hj;<
Lah\ )- \r;h( uh88{; Q5 y({ho .g.Ii )- a)0a8( )jhuucoh\{, `)-8{h;)j0, hj; ah- 8)\\8{ \r ;r ?)\a o{h8 )j\{88)0{ju{2 !rsuh88{; Q5 uhj K{ E{o( [r?{o/c8 -{houa \rr8, hjh8(\)u- \rr8, ;h\h `)j)j0 \rr8, )\ uhj K{ hj(\a)j0 Kc\ o{h8 )j\{88)0{ju{2 La(w }{uhc-{ \a{ ~`c-u8{~ )- jr\ {jrc0a2 !rsuh88{; Q5 8hu6- \a{ /r88r?)j0 \oh)\-<
QK-\ohu\ \a)j6)j0 s )\ uhj rj8( ur`K)j{ ?ah\ uhj K{ /rcj; rj \a{ )j\{oj{\, h8`r-\ h8?h(- )0jro)j0 8)u{j-{- hj; ur``)\\)j0 )j\{88{u\ch8 [or[{o\( \a{/\2 yK8h`{ \a{ hc\aro- r/ \a{ Q5i 5\ 8hu6- hK)8)\( \r /ro0{\ s jh\coh8 ?h( r/ -ro\)j0 )`[ro\hj\ hj; jr\ )`[ro\hj\ \a)j0-2 5\q- 0or?\a o{-{`K8{- oh\a{o \a{ uhju{o 0or?\a \ahj \a{ 0or?\a ;o)E{j K( {j;8{-- jr\s/ro0)E)j0 \o)h8s/h)8co{ h[[orhua c-{; K( {Er8c\)rj /ro K)88)rj- ({ho-2
Zj \a{ r\a{o ahj;, -rsuh88{; Q5 `)`)u- )j\{88)0{ju{ E{o( ?{8822
v)\a{o ?h(, 4## ur``)\\{{ ;{u);{; \r )juro[roh\{ Ac)u6!ro\ )j-\{h; r/ z{o0{!ro\ \r )\- !DW 8)Koho( /cju\)rj std::sort yur`K)j{; ?)\a 5j-{o\)rj!ro\ /ro \a{ -`h88{-\ -)M{-i, [orKhK8( K{uhc-{ r/ )\- -[{{;, E{o-h\)8)\(, hj; )js[8hu{ -ro\)j02
!\o)j0- )j \a{ Kc//{o uhj K{ hj( -)M{, Kc\ \a{ ur`[ho)-rj )- ;rj{ rj8( c[ \r \a{ 8{j0\a -[{u)/){; K( \a{ [hoh`{\{o2 Da{ [hoh`{\{o ;{/hc8\ Eh8c{ )- kC2 Da{ Eh8c{ )- u8h`[{; \r \a{ ohj0{ :*k, .gCl32 Q j{{; \r -ro\ -\o)j0- hKrE{ 8{j0\a .gCl )- E{o( oho{2
Hro -\o)j0 \([{- rj8(, \a{ h80ro)\a` c-{- \a{ FvQ^ h88ruh\)rj r/ )j\{ojh8 Kc//{o- huuro;)j0 \r \a{ [hoh`{\{o Eh8c{ \r hEr); -\hu6 rE{o/8r?2 Hro jc`{o)u Eh8c{ \([{- \a{ !DQ4b h88ruh\)rj r/ )j\{ojh8 Kc//{o- )- -c//)u){j\2
Da{ hissort.hpp, algorithms.hpp hj; comparison_tests.cpp -rcou{ ur;{ /)8{- ahE{ \r K{ ur`[)8{;2
Yr\{ \ah\ }cKK8{!ro\, !{8{u\)rj!ro\, 5j-{o\)rj!ro\, Ac)u6!ro\, z{o0{!ro\ )`[8{`{j\h\)rj- )j \a{ algorithms.hpp ho{ jr\ [ho\ r/ \a{ a)--ro\ [hu6h0{, hj; )\ )- o{-\o)u\{; \r o{s;)-\o)Kc\{ \a{`2 Da{-{ )`[8{`{j\h\)rj- ahE{ rj{shj;srj8( [co[r-{ hj; \ah\ )- \r ur`[ho{ \a{)o -[{{; ?)\a \a{ a)--ro\ h80ro)\a`2 Qj(rj{ uhj c-{ a)-fa{o r?j )`[8{`{j\h\)rj- /ro ur`[ho)-rj \{-\-2 Da{ algorithms.hpp /)8{ uhj K{ -6)[[{; h8\r0{\a{o )/ \a{ 0rh8 )- \r ur`[ho{ -[{{; ?)\a \a{ std::sort rj8(2
Dr uahj0{ Eh8c{ \([{, urj\h)j{o -)M{f\([{, )\{oh\ro \([{, ro \a{ -ro\ ro;{o, nc-\ ur``{j\fcjur``{j\ [ho\)uc8ho \([{- )j \a{ `h)jyi /cju\)rj2 }{?ho{ r/ Kc//{o !5Ov ?a{j cjur``{j\)j0 \a{ }cKK8{!ro\ h80ro)\a` /ro ur`[ho)-rj y-{{ runAlgorithm() /cju\)rj h\ \a{ Kr\\r`i, )\ uhj K{ E{o( -8r?<
Dr hua){E{ `h|)`c` [{o/ro`hju{, \a{ /r88r?)j0 R44 ur`[)8{o r[\)rj- uhj K{ c-{;<
Rr \r -{{ \a{ \{-\ o{-c8\-< 4r`[ho)-rj 4aho\- Da{ -rcou{ ur;{- a)--ro\s*2*2M)[< Tr?j8rh;
Tr?j8rh;- ho{ ucoo{j\8( cjhEh)8hK8{ K{uhc-{ \a{ h80ro)\a` )- )j [{{oso{E){? [oru{-- K{/ro{ [cK8)uh\)rj2 Da{ {j; r/ \a{ o{E){? ?)88 K{ hjjrcju{; rj \a)- ?{K [h0{2 o{h; `ro{222
Da{ h80ro)\a` )- h jrE{8\( )jE{j\)rj ;{E{8r[{; /or` -uoh\ua hj; ah- jr o{-{`K8hju{ \r hj( {|)-\)j0 -ro\)j0 h80ro)\a`-, -{{ \a{ uah[\{o q^co{ E- Z[\)`)M{; 9{o-)rj K{8r?q2
!{j; `{ h `{--h0{ )/ (rc ho{ )j\{o{-\{; y-{{ 8)j6 \r \a{ 4rj\hu\ Hro` h\ \a{ Kr\\r`i2 5/ (rc ahE{ ;rcK\- ro \{uaj)uh8 'c{-\)rj-, [8{h-{ cj;{o-\hj; \ah\ \a{-{ uhjq\ K{ hj-?{o{; ;co)j0 \a{ o{E){? [oru{--2
!{j; `{ h `{--h0{ )/ (rc ho{ )j\{o{-\{; y-{{ 8)j6 \r \a{ 4rj\hu\ Hro` h\ \a{ Kr\\r`i2 5/ (rc ahE{ ;rcK\- ro \{uaj)uh8 'c{-\)rj-, [8{h-{ cj;{o-\hj; \ah\ \a{-{ uhjq\ K{ hj-?{o{; ;co)j0 \a{ o{E){? [oru{--2
Da{ h80ro)\a` ah- \a{ /r88r?)j0 \oh)\-<
- jrjsur`[ho)-rj -ro\
- )js[8hu{ -ro\
- 0{j{oh\)E{ 11
- [ho\)h8 -ro\)j0
1 Ac)u6!ro\ h- \a{ /h-\{-\ -ro\)j0 h80ro)\a` )- [cK8)u8( {`Kohu{; urj-{j-c-, h8\arc0a \a{o{ ho{ r\a{o r[)j)rj-2
11 R{j{oh\)E{ h262h2 qjr\s-\hK8{q )j \a{ -ro\)j0 \{o`)jr8r0( `{hj- )\ uhjjr\ 0hcohj\{{ ro;{o r/ \a{ -h`{ Eh8c{- /or` \a{ ro)0)jh8 Kc//{o2 La)8{ \a{ `r-\ r/ \)`{ )\ 6{{[- ro)0)jh8 ro;{o r/ \a{ -h`{ Eh8c{-, \a{o{ ho{ [ho\- r/ \a{ h80ro)\a` \ah\ uhj q0{j{oh\{q Eh8c{- )j-\{h; r/ ur[()j0 \a{`2
^co{ E- Z[\)`)M{; 9{o-)rj
Da{ [co{ h80ro)\a` )\-{8/ )- YZD h ur`K)jh\)rj r/ r\a{o -ro\)j0 h80ro)\a`-, ar?{E{o \r hua){E{ \a{ a)0a{-\ [r--)K8{ [{o/ro`hju{,
)\ uhj r[\)rjh88( c-{ \a{ 5j-{o\)rj!ro\ h80ro)\a` /ro \a{ -`h88 -)M{- K{8r? C. 1112
Da{ 5j-{o\)rj!ro\ )- jr\ E{o( /h-\ h80ro)\a` )j 0{j{oh8, Kc\ /ro \a{ E{o( -`h88 -)M{-, )\ rc\[{o/ro`- hj(\a)j0 {8-{2 Da{ -h`{ r[\)`)Mh\)rj h[[orhua )- c-{; )j \a{ 4## !DW std::sort /cju\)rj s h a(Ko); 5j\or!ro\ h80ro)\a`, ?a)ua c-{- \a{ Ac)u6!ro\, F{h[!ro\, Kc\ /ro -`h88 )j\{oEh8 -)M{-, )\ -?)\ua{- \r \a{ 5j-{o\)rj!ro\2
5\ )- )`[ro\hj\ \r 6jr? \a{ ;)-\)u\)rj K{\?{{j [co{ Ac)u6!ro\ hj; std::sort, hj; -)`)8ho8(, K{\?{{j [co{ a)--ro\ hj; r[\)`)M{; a)--ro\2 Da{o{/ro{ \r K{ /h)o, rj8( \a{ r[\)`)M{; a)--ro\ -arc8; K{ ur`[ho{; \r \a{ std::sort, ro \r -)`)8ho r[\)`)M{; a(Ko); h80ro)\a`-2 Da{ r[\)`)M{; a)--ro\ ?h- c-{; )j \a{ ur`[ho)-rj \{-\- K{8r?, hj; \a{ r[\)`)M{; E{o-)rj ah- h8-r K{{j )juro[roh\{; )j\r \a{ r//)u)h8 -rcou{ ur;{ o{8{h-{2
Hro \a{ -`h88{-\ -)M{- K{8r? I, a)--ro\ nc-\ -?h[- \a{ Eh8c{- c-)j0 )/s{8-{ K8ru6-2
111 }{uhc-{ C. )- \a{ hj-?{o \r \a{ c8\)`h\{ 'c{-\)rj r/ 8)/{, \a{ cj)E{o-{, hj; {E{o(\a)j0222
})0sZ Yr\h\)rj
Da{ a)--ro\ h80ro)\a` )- Eh8c{ \([{ ;{[{j;{j\, \a{o{/ro{ \a{o{ )- jr -)j08{ {|[o{--)rj \r ;{\{o`)j{ )\- {//)u){ju( ?)\a })0sZ jr\h\)rj2
5\ ?rc8; rj8( K{ [r--)K8{ \r `h6{ orc0a {-\)`h\)rj- r/ \a{ ?ro-\ hj; \a{ K{-\ -u{jho)r- /ro {hua [ho\)uc8ho Eh8c{ uh\{0ro( \([{,
?a)ua ?rc8; {j; c[ ?)\a -{E{oh8 })0sZ {|[o{--)rj-2
z{`ro( Q88ruh\)rj G{'c)o{`{j\-
F)--ro\ ;r{- jr\ j{{; `cua `{`ro( h88ruh\)rj-2 5\ h88ruh\{- )\- )j\{ojh8 Kc//{o- rj \a{ !DQ4b /ro h88 jc`{o)u Eh8c{ \([{-2
Da{ FvQ^ h88ruh\)rj- ho{ o{'c)o{; rj8( /ro -\o)j0 Eh8c{ \([{-, K{uhc-{ -\o)j0- uhj ahE{ Eho)rc- cj[o{;)u\hK8{ 8{j0\a-2
vhua o{uco-)E{ uh88 h88ruh\{- C 6} Kc//{o rj \a{ !DQ4b2 Hro jc`{o)u Eh8c{ \([{-, \a{ /r88r?)j0 -c``ho( !DQ4b h88ruh\)rj- uhj K{ `h;{<
- lsK)\ y-)0j{;fcj-)0j{; uahoi s C 6}
- *ksK)\ y-)0j{;fcj-)0j{; -aro\ )j\i s l 6}
- >.sK)\ y-)0j{;fcj-)0j{; )j\i s *k 6}
- kCsK)\ y-)0j{;fcj-)0j{; 8rj0i s >. 6}
- *.lsK)\ yjrjs-\hj;ho; \([{-i s kC 6}
^ho\)h8 !ro\)j0
F)--ro\ ah- h cj)'c{ /{h\co{ \ah\ h88r?- {ho8( {|)\ /or` \a{ h80ro)\a` [oru{;co{ \r hua){E{ [ho\)h8 -ro\)j0 K( 8)`)\)j0 \a{ o{uco-)rj ;{[\a2
5\ uhj K{ )`h0)j{; h- hj h8`r-\ -ro\{; hooh( ?)\a h jr)-{2 T{[{j;)j0 rj \a{ Eh8c{ \([{ K)\s8{j0\a, \a{o{ ho{ \a{ /r88r?)j0 `h|)`c` o{uco-)rj ;{[\a-<
- lsK)\ Eh8c{ \([{ s `h|2 * yjr o{uco-)rj-i
- *ksK)\ Eh8c{ \([{ s `h|2 . o{uco-)rj-
- >.sK)\ Eh8c{ \([{ s `h|2 C o{uco-)rj-
- kCsK)\ Eh8c{ \([{ s `h|2 l o{uco-)rj-
- *.lsK)\ Eh8c{ \([{ s `h|2 *k o{uco-)rj-
!c[[ro\{; 9h8c{ D([{-
Q88 4f4## -\hj;ho; \([{- hj; -r`{ jrjs-\hj;ho; \([{- ho{ -c[[ro\{;2 }{uhc-{ -\hj;ho; 4f4## \([{- uhj ahE{ ;)//{o{j\ K)\ 8{j0\a-
rj ;)//{o{j\ Z! [8h\/ro`-, )j\{0oh8 \([{- ho{ {|[o{--{; )j \a{ K)\s8{j0\a /ro`2
Z/ urco-{, hj( 6)j; r/ jr\h\)rj r/ 4f4## \([{ uhj K{ c-{; )j hj )`[8{`{j\)j0 [or0oh`2 - int8_t, uint8_t, int16_t, uint16_t, int32_t, uint32_t, int64_t, uint64_t
!\hj;ho; 4f4## -)0j{;fcj-)0j{; )j\{0oh8 \([{-< uaho, -aro\, )j\, 8rj0, 8rj0 8rj0 - __int128, int128_t, uint128_t,
Yrjs-\hj;ho; 4f4## -)0j{;fcj-)0j{; )j\{0oh8 \([{- -c[[ro\{; K( R44f48hj0 ur`[)8{o-2 - float, double
H8rh\ hj; ;rcK8{ \([{- ho{ -\hj;ho; 5vvv JIC -)j08{ hj; ;rcK8{ [o{u)-)rj /8rh\)j0 [r)j\ \([{-2 - __float128, long double
Da{ UU/8rh\*.l )- 5vvv JIC 'ch;oc[8{ [o{u)-)rj /8rh\)j0 [r)j\ \([{2 !r`{ [8h\/ro`-fur`[)8{o- `h( jr\ -c[[ro\ )\2 Da{ 8rj0 ;rcK8{ \([{ )- jrjs-\hj;ho; -rsuh88{; |lJ {|\{j;{; [o{u)-)rj /8rh\)j0 [r)j\ \([{, hj; ah- Eho)rc- )j\{o[o{\h\)rj-2 Hro R44f48hj0 ur`[)8{o-, \a{ 8rj0 ;rcK8{ \([{ )- c-c-h88( lgsK)\- 8{j0\a y-r`{\)`{- VksK)\-i {|[hj;{; \r *.lsK)\- y[h;;{; ?)\a M{or K)\-i2 Hro z)uor-r/\ z!94 ur`[)8{o, \a{ 8rj0 ;rcK8{ \([{ )- nc-\ hj h8)h- /ro ;rcK8{2 Hro r\a{o-, \a{ 8rj0 ;rcK8{ uhj K{ \a{ -h`{ h- UU/8rh\*.l2 5/ \a{ ur`[)8{o -c[[ro\- \a{-{ jrjs-\hj;ho; \([{-, \a{ a)--ro\ h80ro)\a` uhj -c[[ro\ hj( /8rh\)j0 [r)j\ 8{j0\a )/ \a{ K)\s/ro`h\ )- p-)0j # {|[rj{j\ # /ohu\)rj=2 - std::string, std::wstring, std::u16string, std::u32string
Da{ -\o)j0 \([{- ?)\a uahohu\{o -)M{-<
QY!5 y*sK(\{i, _DHs*k y.sK(\{-i, _DHs>. yCsK(\{-i, _DHsl y*s\rsC K(\{-, Eho)rc- 8{j0\ai2
!c[[ro\{; 4rj\h)j{o D([{-
!)`)8ho8(, 8)6{ )j r\a{o -ro\)j0 h80ro)\a`-, {202 std::sort, rj8( urj\)jcrc- hooh( yohj;r` huu{--i urj\h)j{o \([{- ho{ -c[[ro\{;2
W)j6{;s8)-\ urj\h)j{o- y-{'c{j\)h8 huu{--i, {202 std::list, ahE{ \a{)o `h)j h;Ehj\h0{ )j /h-\ ohj;r` )j-{o\)rj hj; ;{8{\)rj, {-[{u)h88( /ro 8ho0{ ;h\h,
Kc\ \a{( ho{ jr\ -c)\hK8{ /ro oh[); -ro\)j02 Q8-r, /ro jrjsur`[ho)-rj h80ro)\a`-, )\ )- `hj( \)`{- {E{j )`[r--)K8{ \r c-{ 8)j6{;s8)-\-2 - std::array, std::vector
Hro?ho; ro o{E{o-{ )\{oh\ro- uhj K{ c-{; h- )j[c\ [hoh`{\{o- )j \a{ /cju\)rj uh882 - std::deque
Hro?ho; ro o{E{o-{ )\{oh\ro- uhj K{ c-{; h- )j[c\ [hoh`{\{o- )j \a{ /cju\)rj uh882 - raw 4f4## hooh(
5j-\{h; r/ )\{oh\ro- \a{ oh? [r)j\{o- ho{ c-{; h- )j[c\ [hoh`{\{o-2
!c[[ro\{; ^or0oh``)j0 Whj0ch0{-
- 4f4##
Da{ o{h-rj )- rKE)rc-<
4f4## )- 8r?s8{E{8 yhj; h8-r a)0as8{E{8i ?);{s-[o{h; /8{|)K8{ 8hj0ch0{ r[\)`)M{; /ro -[{{;2 vE{o( -uo)[\ ro ocj\)`{sKh-{; [or0oh``)j0 8hj0ch0{ y{202 7hEh, 7hEh!uo)[\, 4+, ^F^, ^(\arj, D([{!uo)[\, {\u2i, ahE{ )\- r?j )j\{o[o{\{o ro ocj\)`{ uro{ ?o)\\{j )j h 8r?s8{E{8 8hj0ch0{, c-c-h88( )j 4f4## yro {E{j )j \a{ 4^_ h--{`K8(i2 vE{o( ?{K Kor?-{o, ;h\hKh-{ {j0)j{, ro hj( -[{{;s\a)o-\( h[[8)uh\)rj )`[8{`{j\- )\- -[{{; uo)\)uh8 [ho\- )j \a{ 8r?s8{E{8 8hj0ch0{2
5/ (rc j{{; \r ahE{ )`[8{`{j\{; a)--ro\ h80ro)\a` )j h [or0oh``)j0 8hj0ch0{ r/ (rco uar)u{, \a{j h-6 ;{E{8r[{o- r/ \a{ 8hj0ch0{ \r r//)u)h88( )juro[roh\{ )\ h- h 8)Koho( /cju\)rj \r hua){E{ `h|)`c` -[{{;2 Fr?{E{o, -cua h -\{[ ?rc8; o{'c)o{ [{o`)--)rj /or` \a{ h80ro)\a` r?j{o2 Lo)\)j0 \a)- h80ro)\a` )j hj )j\{o[o{\{; 8hj0ch0{ )\-{8/ ;r{-jq\ `h6{ hj( -{j-{, )\ ?)88 o{-c8\ )j [{o/ro`hu{ -8r?{o \ahj \a{ 8hj0ch0{q- h8o{h;( hEh)8hK8{ -ro\)j0 /cju\)rj-2
v|h`[8{ r/ _-h0{ )j 4## ^or0oh`
5\ )- h- {h-( h- )\ 0{\-, nc-\ )ju8c;{ hissort.hpp )j (rco 4## -rcou{ ur;{2
v|h`[8{ r/ _-h0{ )j 4s8hj0ch0{ ^or0oh`
H)o-\, \a{ hissort.hpp, hissort_cwrap.h hj; hissort_cwrap.cpp
/)8{- y-{{ K{8r?i j{{; \r K{ ur`[)8{; )j\r h -\h\)u 8)Koho(2
Da)- -\{[ )- j{u{--ho( K{uhc-{ \a{ h80ro)\a` )\-{8/ )- ?o)\\{j )j \a{ 4## ?)\a \{`[8h\{-2
Zju{ \a)- -\{[ )- ;rj{, )\ ;r{-jq\ ahE{ \r K{ o{[{h\{;2
Da{ /r88r?)j0 R44 ur`[)8{o ur``hj; uo{h\{- libhissort.a W)jc| -\h\)u 8)Koho(<
gcc -c -O1 -o hissort_cwrap.o hissort_cwrap.cpp
ar rcs libhissort.a hissort_cwrap.o
H)jh88(, \a{ libhissort.a 8)Koho( uhj K{ 8)j6{; ?)\a \a{ usage.c <
hj; ur`[)8{; )j\r hissortest {|{uc\hK8{ ?)\a \a{ /r88r?)j0 ur``hj;<
gcc -O1 -o hissortest usage.c libhissort.a
!rsuh88{; Qo\)/)uh8 5j\{88)0{ju{
Q5 h8-r 6jr?j h- Qo\)/)u)h8 5j\{8)0{ju{ ?h- YZD c-{; )j \a{ ;{E{8r[`{j\ r/ \a)- h80ro)\a`2
Yr\ {E{j -8)0a\{-\ {--{ju{ r/ )\2 5/ (rc j{{; h [orr/, \a{j (rc -arc8; h-6 (rco-{8/ \a{-{ -)`[8{ 'c{-\)rj-<
- La( jrKr;( ah- )jE{j\{; -)`)8ho h80ro)\a` -r /how
- La( ?{ -\)88 ho{jq\ )jcj;h\{; ?)\a j{? Q5 -r/\?ho{ h80ro)\a`-w
- La( \a{o{ ho{ jr Q5 jrE{8\( )jE{j\)rj-, Kc\ rj8( )`[orE{`{j\- ro ur`K)jh\)rj- r/ ?ah\ ?h- h8o{h;( )jE{j\{;w
Lah\ )- \r;h( uh88{; Q5 y({ho .g.Ii )- a)0a8( )jhuucoh\{, `)-8{h;)j0, hj; ah- 8)\\8{ \r ;r ?)\a o{h8 )j\{88)0{ju{2 !rsuh88{; Q5 uhj K{ E{o( [r?{o/c8 -{houa \rr8, hjh8(\)u- \rr8, ;h\h `)j)j0 \rr8, )\ uhj K{ hj(\a)j0 Kc\ o{h8 )j\{88)0{ju{2 La(w }{uhc-{ \a{ ~`c-u8{~ )- jr\ {jrc0a2 !rsuh88{; Q5 8hu6- \a{ /r88r?)j0 \oh)\-<
QK-\ohu\ \a)j6)j0 s )\ uhj rj8( ur`K)j{ ?ah\ uhj K{ /rcj; rj \a{ )j\{oj{\, h8`r-\ h8?h(- )0jro)j0 8)u{j-{- hj; ur``)\\)j0 )j\{88{u\ch8 [or[{o\( \a{/\2 yK8h`{ \a{ hc\aro- r/ \a{ Q5i 5\ 8hu6- hK)8)\( \r /ro0{\ s jh\coh8 ?h( r/ -ro\)j0 )`[ro\hj\ hj; jr\ )`[ro\hj\ \a)j0-2 5\q- 0or?\a o{-{`K8{- oh\a{o \a{ uhju{o 0or?\a \ahj \a{ 0or?\a ;o)E{j K( {j;8{-- jr\s/ro0)E)j0 \o)h8s/h)8co{ h[[orhua c-{; K( {Er8c\)rj /ro K)88)rj- ({ho-2
Zj \a{ r\a{o ahj;, -rsuh88{; Q5 `)`)u- )j\{88)0{ju{ E{o( ?{8822
^{o/ro`hju{ D{-\-
D{-\- o{-c8\- uhj Eho( rj ;)//{o{j\ aho;?ho{ & -r/\?ho{ urj/)0coh\)rj-,
\a{o{/ro{ )`[ro\hj\ /ro \a{ ur`[ho)-rj )- \a{ oh\)r h`rj0 [ho\)uc8ho h80ro)\a`- /ro {hua -\{[,
)2{2 /ro {hua Eh8c{ \([{ hj; Kc//{o -)M{2 vE{j \a{j \a{ o{-c8\- uhj K{ Er8h\)8{,
K{uhc-{ \a{ Kc//{o )- h8?h(- /)88{; ?)\a ;)//{o{j\ ohj;r` jc`K{o-2 QE{oh0)j0 o{-c8\ jc`K{o- r/ `c8\)[8{ \{-\ ocj- ?)\a
/o{-a ohj;r` Kc//{o /ro {hua -\{[ )- j{u{--ho( \r 0{\ \([)uh8 o{-c8\-2 La( ?h- z{o0{!ro\ jr\ )ju8c;{; )j \a{ D{-\-
5\ ?h- ro)0)jh88( )ju8c;{;, Kc\ 8h\{o o{`rE{; K{uhc-{ )\- [{o/ro`hju{ ?h- jr\ ;)-\)ju\ {jrc0a /or` \a{ Ac)u6!ro\2
!r`{ -rcou{- u8h)` \ah\ z{o0{!ro\ h80ro)\a` )- /h-\{o \ahj Ac)u6!ro\, ?a)ua )- -r`{\)`{- \oc{, hj; -r`{\)`{- jr\2
Qjr\a{o o{h-rj )- \ah\ \a{ z{o0{!ro\ )- rc\sr/s[8hu{ h80ro)\a`, )2{2 )\ o{'c)o{- \r h88ruh\{ j{? Kc//{o /ro -ro\{; hooh(2
La)8{ )\ )- [r--)K8{ \r uo{h\{ )js[8hu{ z{o0{!ro\, \a{ [{o/ro`hju{ ;)//{o{ju{- K{\?{{j a)--ro\ hj; z{o0{!ro\
?rc8;jq\ K{ `cua ;)-\)ju\ /or` \a{ a)--ro\ hj; Ac)u6!ro\2 v)\a{o ?h(, 4## ur``)\\{{ ;{u);{; \r )juro[roh\{ Ac)u6!ro\ )j-\{h; r/ z{o0{!ro\ \r )\- !DW 8)Koho( /cju\)rj std::sort yur`K)j{; ?)\a 5j-{o\)rj!ro\ /ro \a{ -`h88{-\ -)M{-i, [orKhK8( K{uhc-{ r/ )\- -[{{;, E{o-h\)8)\(, hj; )js[8hu{ -ro\)j02
D{-\)j0 ?)\a !\o)j0-
Hro -\;<<-\o)j0 Eh8c{ \([{- yhj; )\- Eho)h\)rj-i \a{o{ )- r[\)rjh8 [hoh`{\{o \r -{\ `h|)`c` -\o)j0 8{j0\a \r ur`[ho{2
Hro jc`{o)u Eh8c{ \([{-, \a{ [hoh`{\{o )- )0jro{;<
hissort(buffer.begin(), buffer.end(), std::less<>{}, 64);
!\o)j0- )j \a{ Kc//{o uhj K{ hj( -)M{, Kc\ \a{ ur`[ho)-rj )- ;rj{ rj8( c[ \r \a{ 8{j0\a -[{u)/){; K( \a{ [hoh`{\{o2 Da{ [hoh`{\{o ;{/hc8\ Eh8c{ )- kC2 Da{ Eh8c{ )- u8h`[{; \r \a{ ohj0{ :*k, .gCl32 Q j{{; \r -ro\ -\o)j0- hKrE{ 8{j0\a .gCl )- E{o( oho{2
Hro -\o)j0 \([{- rj8(, \a{ h80ro)\a` c-{- \a{ FvQ^ h88ruh\)rj r/ )j\{ojh8 Kc//{o- huuro;)j0 \r \a{ [hoh`{\{o Eh8c{ \r hEr); -\hu6 rE{o/8r?2 Hro jc`{o)u Eh8c{ \([{- \a{ !DQ4b h88ruh\)rj r/ )j\{ojh8 Kc//{o- )- -c//)u){j\2
^or0oh` /ro ^{o/ro`hju{ D{-\- )j 4##
Da{ /r88r?)j0 \{-\ [or0oh` ?h- c-{; \r 0{j{oh\{ \a{ ur`[ho)-rj uaho\- K{88r?2
Da{ [or0oh` uo{h\{- h urj\h)j{o /)88{; ?)\a ohj;r` jc`K{o-, -ro\- \a{ Eh8c{- )j \a{ Kc//{o, `{h-co{- -\ho\ hj; -\r[ \)`{s-\h`[-,
\a{j ua{u6- {E{o( Eh8c{- ?a{\a{o \a{ Kc//{o ?h- -ro\{; uroo{u\8(, hj; {E{j\ch88( [o)j\- -r`{ Kc//{o Eh8c{- \r \a{ urj-r8{2 Da{ hissort.hpp, algorithms.hpp hj; comparison_tests.cpp -rcou{ ur;{ /)8{- ahE{ \r K{ ur`[)8{;2
Yr\{ \ah\ }cKK8{!ro\, !{8{u\)rj!ro\, 5j-{o\)rj!ro\, Ac)u6!ro\, z{o0{!ro\ )`[8{`{j\h\)rj- )j \a{ algorithms.hpp ho{ jr\ [ho\ r/ \a{ a)--ro\ [hu6h0{, hj; )\ )- o{-\o)u\{; \r o{s;)-\o)Kc\{ \a{`2 Da{-{ )`[8{`{j\h\)rj- ahE{ rj{shj;srj8( [co[r-{ hj; \ah\ )- \r ur`[ho{ \a{)o -[{{; ?)\a \a{ a)--ro\ h80ro)\a`2 Qj(rj{ uhj c-{ a)-fa{o r?j )`[8{`{j\h\)rj- /ro ur`[ho)-rj \{-\-2 Da{ algorithms.hpp /)8{ uhj K{ -6)[[{; h8\r0{\a{o )/ \a{ 0rh8 )- \r ur`[ho{ -[{{; ?)\a \a{ std::sort rj8(2
Dr uahj0{ Eh8c{ \([{, urj\h)j{o -)M{f\([{, )\{oh\ro \([{, ro \a{ -ro\ ro;{o, nc-\ ur``{j\fcjur``{j\ [ho\)uc8ho \([{- )j \a{ `h)jyi /cju\)rj2 }{?ho{ r/ Kc//{o !5Ov ?a{j cjur``{j\)j0 \a{ }cKK8{!ro\ h80ro)\a` /ro ur`[ho)-rj y-{{ runAlgorithm() /cju\)rj h\ \a{ Kr\\r`i, )\ uhj K{ E{o( -8r?<
4r`[)8{o Z[\)`)Mh\)rj
Da{ \{-\ [or0oh` ?h- ur`[)8{; rj _Kcj\c W)jc| ?)\a R44fR## ur`[)8{o ?)\a Zg, Z*, Z. r[\)`)Mh\)rj r[\)rj-2
^o{-{j\{; o{-c8\- )j \a{ uaho\- K{8r? ho{ rj8( /ro Z* r[\)rj2 Da{o{ ?{o{ jr o{`ho6hK8{ [{o/ro`hju{ ;)//{o{ju{- h`rj0 Z*, Z., Z> r[\)rj-,
{|u{[\ /ro r[\)rj Zg yjr r[\)`)Mh\)rji, ?)\a ?a)ua \a{ [{o/ro`hju{ ?h- `cua -8r?{o /ro h88 h80ro)\a`-,
h8\arc0a \a{ a)--ro\ o{-c8\ oh\)r- ?{o{ o{8h\)E{8( K{\\{o2 5\ )- o{ur``{j;{; \r c-{ ur`[)8{o -[{{; r[\)`)Mh\)rj r[\)rj
?a{j ur`[)8)j0 a)--ro\, ro hj( r\a{o -ro\)j0 h80ro)\a`2 Dr hua){E{ `h|)`c` [{o/ro`hju{, \a{ /r88r?)j0 R44 ur`[)8{o r[\)rj- uhj K{ c-{;<
gcc -Ofast -march=native -mtune=native -fprefetch-loop-arrays -fno-exceptions
Fho;?ho{f!r/\?ho{ 4rj/)0coh\)rj _-{; )j \a{ D{-\-
- 4^_< 5j\{8yGi 4ro{yDzi )Vs*CVggF% .2.g RFM
- R^_< Y95T5Q R{Hrou{ GD% CgJg Wh[\r[
- GQz< >. R}
- Z!< _Kcj\c W)jc| kCsK)\
D{-\- o{-c8\- /ro Eho)rc- Kc//{o -)M{- hj; Eh8c{ \([{-<
* 6}
C 6}
*k 6}
kC 6}
.Ik 6}
* z}
C z}
*k z}
kC z}
.Ik z}
© Q[{|4aho\- ho{ c-{; )j \a)- ?{K [h0{
© ^o)-`7! )- c-{; /ro -rcou{ ur;{ a)0a8)0a\)j0
Da)- ?{Ks[h0{ )- jr\ c-)j0 urr6){-, )\ ;r{-jq\ \ohu6 (rco hu\)E)\( jro ur88{u\- hj( ;h\h2
