Para muchas cosas y también para la Ordenación de Vectores el refranero dice: “Ni son todos los que están, ni están todos los que son”, los que importan están. Todos ellos persiguen el mismo resultado, ordenar los elementos de acuerdo con algún criterio. También existen algunos absurdos como el Bogosort, nombrado de muchas formas pero con el mismo significado, “hazlo lo peor que puedas” y otros que están cerca de él o en desuso (Monkey, Slow, Stupid, … ) que no les prestaré atención.
Los algoritmos están escritos en Java, de forma muy portable a otros lenguajes. (Para los “Puristas” de la programación orientada a objetos, está claro que podría haber incluido determinadas operatorias en clases, procedimientos, polimorfismo, etc., pero el objeto de los programas no está dirigido a los que ya saben). Estoy bastante seguro de que la codificación es correcta, pero no garantizo que pueda existir algún error oculto.
Tened en cuenta que las herramientas de desarrollo disponen de librerías que los implementan, por tanto, no sería necesario plantearnos que los debemos programar, salvo por curiosidad o aprendizaje, No reinventar la rueda es un avance sustancial. Algo importante antes de nada, recordad que la velocidad de ordenación no solo depende del algoritmo, sino de una combinación de: la naturaleza de los datos, cantidad de elementos, cantidad de bits por elemento, cantidad de bits por palabra de la computadora y hasta hace algunos años, de los dispositivos que los almacenaban.
Por otro lado y desafortunadamente, algunos de ellos están parcialmente documentados, en la labor de investigación no he encontrado información suficiente, o no he tenido tiempo de escribirlos, realizar análisis teóricos, cálculos, etc., además, los nuevos algoritmos no son fáciles de implementar y más aún sin máquinas grandes, pero “ahí están, como la puerta de Alcalá”.
Respecto a los algoritmos clasificados como paralelos “P”. Son los algoritmos desarrollados para procesos en paralelo y/o red, pueden ejecutarse en distintas arquitecturas: Bruijn, Hypercube, Mesh, PRAM, etc. Todos ellos también pueden tener una versión en mono procesador y procesar de modo externo o interno. Por otro lado y debido a su alta competitividad, el modo de ordenación y su evaluación en términos de complejidad (O, Ω, Θ) se disipan y se toman los rendimientos en base a la ordenación de TB por minuto, número de nodos, GB de memoria interna, velocidad de red, tipo de dispositivo de almacenamiento y velocidad del mismo, arquitectura (S.O., Hadoop, MapReduce, YARN, HDFS, RAID, …), consumo energético, etc.
? Pulsar en la cabecera de la columna para Clasificar.
Fecha | Nombre | Autor | Metodo | P | Externo | Mejor Ω(n) | Peor O(n) | Media Θ | Memoria | Estable |
---|---|---|---|---|---|---|---|---|---|---|
1.834 | Pigeonhole (Casillero) | J. P. G. Lejeune Dirichlet | Distribución | I | – | – | – | – | – | |
1.880 | Radix | Herman Hollerith | Distribución | I | – | – | – | – | – | |
1.929 | Radix | Leslie J. Comrie | Distribución – Casillero | I | (n × d) | (n × d) | (n × d) | – | – | |
1.938 | Collator | James W.Bryce | Merge | E | – | – | – | – | – | |
1.943 | Plankalkül | Konrad Zuse | Inserción | I | – | – | – | – | – | |
1.945 | Merge | John Von Neumann | Merge | I | (n log n) | (n log n) | (n log n) | O(n) | Est | |
1.946 | Inserción | John Mauchly | Inserción | I | (n) | (n²) | (n²) | O(1) | Est | |
1.946 | Inserción Binaria | John Mauchly | Inserción Binaria | I | (n log n) | (n²) | (n²) | O(1) | Est. | |
1.946 | Balanced Merge | John Mauchly | Merge | E | – | – | – | – | – | |
1.954 | Mathsort | Harold Seward (1.960, Wallace Feurzeig ) | Distribución | I | – | – | – | – | – | |
1.954 | Counting-sort | Harold H. Seward | Distribución – Casillero | (n + k) | (n + k) | (n + k) | – | Est | ||
1.954 | Radix | Harold H. Seward (misil Polaris) | Distribución . Casillero | I | (n × d) | (n × d) | (n × d) | (n + d) | Est | |
1.954 | Bubble (Burbuja) | Edward H Friend | Intercambio – Inserción | I | (n) | (n²) | (n²) | O(1) | Est | |
1.956 | Selección | – | Selección – Inserción | I | (n²) | (n²) | (n²) | O(1) | No | |
1.956 | Pigeonhole (Casillero) | E. J. Isaac y R. C. Singleton | Distribución | I | – | (n + 2R) | (n + 2R) | O( 2R) | Est | |
1.956 | Radix list | Edward H Friend | Radix | E | – | – | – | – | – | |
1.957 | Two-way insertion | David John Wheeler | Inserción – Árbol | I | (n log n) | (n²) | (n log n) | – | – | |
1.958 | Tree sort | Conway M. Berners-Lee | Inserción – Árbol | I | – | – | – | – | – | |
1.958 | Inserción | Hugo Steinhaus | Inserción | I | (n) | (n²) | (n²) | O(1) | Est | |
1.959 | Radix Exchange | P. Hildebrandt, H. Isbitz, H. Rising y J. Schwartz | Intercambio – Bucket – Counting | I | (n(k/b)) | (n(k/b)) | (n(k/b)) | O(n) | Est | |
1.959 | Shellsort | Donald Shell | División – Inserción | I | (n log n) | (n log2 n) | (n log2 n) | O(1) | No | |
1.959 | Quicksort | Antony R. Hoare |
División – Inserción |
I | (n log n) | (n²) | (n log n) | O(log n) | No+Si | |
1.959 | Merge-insertion sort | 1) Stanisław C. Trybuła y Czen Ping 2) L. R. Ford y S. M. Johnson | Inserción – Fusión | I | – | – | – | – | – | |
1.959 | Cascade Merge | B.K. Betz y W.C. Carter | Merge – Inserción | I | – | – | – | – | No | |
1.960 | Cascade Merge | R.L.GiIstad | Merge – Inserción – PolyPhase | I | – | – | – | – | – | |
1.960 | Tree Insertion | K.E..Iversion | Inserción | I | – | – | – | – | – | |
1.962 | Treesort3 | Robert W. Floyd (Predecesor de Heapsort) | Inserción – Quicksort | I | – | (n²) | (log n) | O(n) | Est | |
1.962 | Patience – Solitario | C. L. Mallow (A..S. C. Ross) | Inserción – Selección | I | (n) | (n log n) | – | O(n) | No | |
1.962 | Bubble | Kenneth E. Iverson | Intercambio | I | (n) | (n²) | (n²) | O(1) | Est | |
1.962 | Treesort | R. W. Floyd | Selección – Inserción – Quicksort | I | (n log n) | (n²) | (n log n) | O(1) | No | |
1.962 | Tournament -tree | Kenneth E. Iverson | Selección – Heapsort | (n log n) | (n log n) | (n log n) | (n) | No | ||
1.962 | Oscillator | Sheldon Sobel | Merge | I | – | – | – | – | – | |
1.964 | Heap | J.W.J Willams | Selección – Inserción – Quicksort | I | (n log n) | (2n log n) | (n log n) | O(1) | No | |
1.964 | Treesort3 | R. W. Floyd | Selección – Inserción – Quicksort | I | (n log n) | (n log n) | (n log n) | O(1) | No | |
1.964 | Bitonic | Kenneth E. Batcher | División – Intercambio ( Árbol) | P | E | (log²n) | (log²n) | (log²n) | O(n log²n) | – |
1.964 | Merge-Exchange | Kenneth E. Batcher | Merge – Intercambio | I | – | – | – | – | – | |
1.965 | Quicker | Roger S. Scowen | Quicksort | I | – | – | – | – | – | |
1.968 | OEMS (Odd-Even Merge Sort ) | Kenneth E. Batcher | Merge – Intercambio | P | E | – | n(logn)² | (n) | – | – |
1.969 | Quicksort | R. C. Singleton | Quicksort | I | (n log n) | (n²) | (n log n) | O(1) | No | |
1.969 | List merge | L.J.Woodrum y A.D.Woodall | Merge – Listas | I | – | – | – | – | – | |
1.970 | Qsort | Marteen H. Van Emden | División – Inserción – Quickersort | I | – | – | – | – | – | |
1.970 | Samplesort | W. D. Frazer y A. C. McKellar | División | I | – | (n²) | (nlog² n) | – | – | |
1.972 | Odd-Even (Brick) | Nico Habermann | Intercambio | P | (n²) | (n²) | (n²) | O(n) | Est | |
1.972 | Binary Merge | F.K. Hawang y S. Lin | Merge | I | – | – | – | – | – | |
1.972 | Gyrating sort | R.M.Karp | Merge – Preordenada | I | – | – | – | – | – | |
1.973 | Binary Merge | F.K.Hawang y D.N. Deutsh | Merge | I | – | – | – | – | – | |
1.975 | Boas tree | Peter Van Emde Boas | Árboles | I | (n log log n) | – | – | – | – | |
1.977 | SMCP | C.D. Thompson y H.T. Kung | Fusión – Bitonic – Merge | P | (n) | – | – | – | – | |
1.978 | Binary Merge | C.Christen | Merge | I | – | – | – | – | – | |
1.978 | SedgewickFast | Sedgewick | Quicksort | I | (n log n) | (n log n) | (n log n) | – | – | |
1.978 | Tape merge | C. Christen | Merge | E | – | – | – | – | – | |
1.979 | Binary Merge | G .K. Manacher | Merge | I | – | – | – | – | – | |
1.979 | Bitonic | David Nassimi y Sartaj Sahni | Bitonic | P |
(n)
|
– | – | – | – | |
1.979 | Tape merge | Paul E. Murphy y Marvin C. Paull | Merge | E | – | – | – | – | – | |
1.980 | Comb | Wlodzimierz Dobosiewicz | Intercambio | I | (n log n) | (n²) | (n²) | O(1) | No | |
1.980 | Proxmap | Thomas A. Standish | División – Bucket | I | (n) | (n²) | (n) | (n) | – | |
1.980 | E-Quicksort | M.C. Monard | División – Quicksort | E | – | – | – | – | – | |
1.980 | Runsort | Curtis R. Cook y Do J. Kim | Inserción – Quicksort | I | – | – | – | – | – | |
1.981 | Smooth | Edsger W. Dijkstra | Selección – Heapsort | I | (nlogn)→(n) | (n log n) | (n log n) | O(1) | No | |
1.981 | Radix | D. Kirkpatrick y S. Reisch | Distribución | I | (n*longitud) | (n*longitud) | (n*longitud) | – | – | |
1.982 | Binary Merge | M. Thanh y T.D. Bui | Merge | I | – | – | – | – | – | |
1.982 | Trisort | Lutz M. Wegner | Quicksort | I | – | – | – | – | Est | |
1.983 | AKS | M. Ajtai, J. Komlós y E. Szemerédi | División – Quicksort | P | Profundo (log n) | – | – | – | – | |
1.983 | Flashsort | J. H. Reif y L. G. Valiant | Distribución | P | I | – | – | – | – | – |
1.983 | Meansort | Dalia Motzkin | Inserción – Quicksort | I | – | – | – | – | – | |
1.983 | Samplesort | Y.C. Chow y J.S. Huang | Samplesort | P | – | – | – | – | – | |
1.984 | EXQUISIT | Hans-Werner Six y Lutz Wegner | División – Inserción – Quicksort | E | (n log n) | (n log n) | (n log n) | – | – | |
1.984 | GOSort | Lutz Michael Wegner | Quicksort | I | – | – | – | – | – | |
1.985 | Bsort | R.L. Wainwright | Quicksort | I | (n log n) | – | – | – | – | |
1.985 | Columnsort | Torn Leighton | OEMS | P | (log n) | – | – | – | – | |
1.985 | Quicksort | D. J. Evans y Nadia Y. Yousif | Quicksort | P | – | – | – | – | – | |
1.985 | SplayTree | Daniel D. Sleator y Robert E. Tarjan | Árboles | I | – | (log n) | – | – | – | |
1.985 | UnShuffle | Art S. Kagel | Merge – Distribution | I | (n) | (kn) | (kn) | – | Est | |
1.986 | Bogo | Andrei Broder y Jorge Stolfi (Lo diseñan como broma) | Aleatorio | I | (n) | (n) | (n * n!) | Infinito | No | |
1.986 | Adaptative Bitonic Sort | G. Bilardi y A. Nicolau | Bitonic | P | E | – | (log²n) | – | – | – |
1.986 | Bucket – Cubeta | Y. Han y R.A. Wagner | Bucket | P | – | – | – | – | – | |
1.986 | OSort | Huang Bing-Chao y Donald E. Knuth | Quicksort | I | – | – | – | – | – | |
1.986 | HyperQuicksort | B. Wagar | Quicksort | P | – | – | – | – | – | |
1.986 | Shear-sort | I. D. Scherson, S. Sen y A. Shamir | Burbuja | P | – | (n1/2 log n) | – | – | – | |
1.987 | Cycle | B. K. Haddon | Selección – Inserción | (n²) | (n²) | (n²) | O(1) | No | ||
1.987 | AKS | Michael S .Paterson | División – Quicksort | P | Profundo (log n) | – | – | – | – | |
1.987 | Bottom-Up-Heapsort | S. Carlsson | Heapsort | I | – | (n log n) + (n log log n) | (n log n) + (n log log n | – | ||
1.987 | Bucket – Cubeta | Torben Hagerup | Bucket | P | – | (log n) | – | – | – | |
1.987 | Qsorte | R.L. Wainwright | Quicksort | I | – | (n²) | – | – | – | |
1.987 | Radix | R. Paige y R.E.Tarjan | Distribución | I | – | (n / H) | – | – | – | |
1.988 | Fusión | Richard Cole | Merge | P | – | (log n) | – | – | – | |
1.989 | Bottom-Up-Heapsort | Ingo Wegener | Heapsort – Quicksort | I | – | (n log n) +(1,1n) | – | – | ||
1.989 | Hillsort | Lutz Michael Wegner y Jukka Teuhola | Heapsort | E | – | – | – | – | – | |
1.989 | Bottom-Up-Heapsort | C.J. McDiarmid y B.A. Reed |
Heapsort – Treesort3 |
I | – | (1,5n log n) – (0,4n) | – | – | – | |
1.989 | Maxtree-sort | Christos Levcopoulos y Ola Petersson | Heapsort – Cartesian-tree | I | (n) | (n log n) | – | (n) | – | |
1.989 | Per-nod-inv | P. C. P. Bhatt, K. Diks, T. Hagerup, V. C. Prasad , T. Radzik y S. Saxena | Permutación | P | – | (log n/log log n) | – | – | – | |
1.989 | MDR-Heapsort | C.J.H McDiarmid y B.A. Reed | Heapsort | I | – | – | – | – | – | |
1.989 | Shear-sort | Isaac D. Scherson, Sandeep Sen y Yiming Ma | Burbuja | P | – | (n) | (n1/2 log n) | – | – | – |
1.989 | Ultrasort | E.D. Reilly y F.D. Federighi | Mathsort | I | – | (n) | – | – | – | |
1.990 | Fusion Tree | Fredman y Willard | Fusión en árbol | I | n (n log n / log log n) | – | – | Lineal | ||
1.991 | Comb | Stephen Lacey y Richard Box | Intercambio | I | (n log n) | (n²) | (n²) | O(1) | No | |
1.991 | Merge Path | Narsingh Deo, Amit Jain y Muralidhar Medid | Bitonic + Fusión | P | – | (log m + log r) | – | – | – | |
1.991 | TMSort y PTMSort | Hiroyasu Hamamura, Miyao Jun’ichi y Shin’ichi Wakabayashi | Tree Merge | P | – | – | – | – | – | |
1.991 | Quicksort-Rotate | B. McDaniel | Quicksort | I | – | (n²) | – | – | – | |
1.991 | Sharesort | Robert Cypher y C. Greg Plaxton | Intercambio – Aleatorio | P | E | – | (log n (log log n)²) | – | – | – |
1.992 | B-Flashsort | William L. Hightower, Jan F. Prins y John H. Reif | División – Flashsort (Reif- Valiant) | P | – | – | – | – | – | |
1.992 | Fast Radix | I.J. Davis | Radix | I | – | – | – | – | ||
1.992 | Packed | Susanne Albers y Torben Hagerup | Radix | P | – | (log n) ² | – | – | – | |
1.993 | Balance Sort | Mark H. Nodine y Jeffrey S. Vitter | Distribución | P | – | – | – | – | – | |
1.993 | Fusión | O. Berkman y U. Vishkin | Merge | P | I | (n²) | (log log log s) | – | – | |
1.993 | Weak – Heapsort | Ronald D. Dutton | Heapsort | I | – | (n – 1)log n + (0,086013n) | (n-0,5)log n – (0,413000n) | – | ||
1.993 | Histogram Sort | V Kale Laxmikant y Krishnan Sanjeev | Samplesort – Hypercube – Binsort | P | – | – | – | – | – | |
1.993 | qsort7 | J.L. Bentley y M.D. McIlroy | Quicksort – función qsort | – | (n²) | – | – | – | ||
1.993 | MDR-Heapsort | Ingo Wegener | Bottom-Up-Heapsort | I | – | (n + 1)log n + (1,086072n) | – | – | – | |
1.993 | Shiftdown-Heapsort | Russel Schaffer y Robert Sedgewick | Bottom-Up-Heapsort | I | – | – | – | – | – | |
1.993 | QuickBM | Jon L. Bentley y M. Douglas McIlroy | Quicksort | I | – | – | – | – | – | |
1.993 | Radix | R. Vaidyanathan, R. P Hartmann y P. K. Varshney | Radix | P | – | – | – | – | – | |
1.993 | Sort-H | Shenfeng Chen y John H. Reif | División – Aleatorio | P | – | ( log n) | – | – | – | |
1.994 | Alpha Sort | Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray y Dave Lomet | Quicksort | P | E | – | – | – | – | – |
1.994 | Forward Radix | Arne Anderson y Stefan Nilson | Radix | I | – | – | – | – | – | |
1.994 | NERS | Arne Anderson y Stefan Nilson | Radix | – | – | – | – | – | ||
1.994 | Sharesort | A. Aggarwal y C.G. Plaxton | Intercambio – Aleatorio | P | E | – | (log n (log log n)²) | – | – | – |
1.994 | Jsort | Jason Morrison | Heap + inserción | I | (n) | (n²) | – | – | No | |
1.994 | Forward Radix Sort (FRS) | Arne Andersson y Stefan Nilsson | Radix | I | ||||||
1.995 | Greed Sort | Mark H. Nodine y Jeffrey S. Vitter | Merge – Bucket | P | E | – | – | – | – | – |
1.996 | Self-Indexed (SIS) | Yingxu Wang | Auto-Indexado | I | (n + m) | (n + m) | (n + m) | (n + m) | – | |
1.996 | DSM | Rakesh Barve y Jeffrey Scott Vitter | Merge | P | E | – | – | – | – | – |
1.996 | Splay | Alistair Moffat, Eddy Gary y Ola Petersson | Inserción – SplayTree | I | – | – | – | – | – | |
1.996 | SRM | Rakesh D. Barve, Edward F. Grove y Jeffrey Scott Vitter | Merge | P | E | – | – | – | – | – |
1.997 | Introsort | David R.Musser | Inserción – Quick+Heap | I | (n) ¿>? | (n log n) | (n log n) | (n log n) | No | |
1.997 | Multikey | J.L. Bentley y R. Sedgewick | MSD-Radix – Quicksort | I | – | – | – | – | ||
1.997 | Flashsort | Karl-Dietrich Neubert | Distribución | I | (n) | (n²) | (n + d) | (0,1n) | – | |
1.998 | Signature | A. Andersson, T. Hagerup, S. Nilsson y R. Raman | Bucket – Aleatorio | I | (n log log n) | – | – | Lineal | – | |
1.998 | UltimateHeapsort | J. Katajainen | Heapsort | I | – | – | – | – | – | |
1.999 | FFS (Faster Suffix Sorting) | N.J. Larsson y k. Sadakane | Quicksort | I | – | (n log n) | – | – | – | |
1.999 | Spsort | Jim Wyllie | Bucket | P | – | – | – | – | – | |
2.000 | Gnome – Stupid sort | Hamid Sarbazi – Azad / Dick Grune | Intercambio | I | (n) | (n²) | (n²) | O(1) | Est | |
2.000 | Weak-Heapsort | Stefan Edelkamp y Ingo Wegener | Heapsort | I | – | – | – | – | – | |
2.000 | Bundlesorting | Yossi Matias, Eran Segal y Jeffrey S. Vitter | Merge | E | – | – | – | – | – | |
2.000 | HMSort | Brad Helmkamp y Keith McCready | Hibrido | P | – | – | – | – | – | |
2.001 | Columnsort | G. Chaudhry, T. H. Cormen y L. F. Wisniewski | OEMS | P | (log n) | – | – | – | – | |
2.001 | DMSort | Aaron Darling y Alex Mohr | Radix | P | – | – | – | – | – | |
2.002 | QuickHeapsort | D. Cantone y G. Cinotti | Quick – Heapsort | I | – | – | – | – | ||
2.002 | Bead – Abacus | Joshua J. Arulanandham, Cristian S. Calude y Michael J. Dinneen | Distribución | P | I | (n log n) | – | O(n²) | Est | |
2.002 | Yiha-Mith | Yijie Han y M. Thorup | Hibrido | – | – | – | Lineal | – | ||
2.002 | PPR (Partitioned Parallel Radix Sort) | Shin-Jae Lee, Minsoo Jeon, Dongseung Kim y Andrew Sohn | Radix | P | – | – | – | – | – | |
2.002 | TimSort | Tim Peters | Inserción – Fusión | I | (n) | (n log n) | (n log n) | (n) | Est | |
2.002 | EP-fast | Hazem M. Bahig, Sameh S. Daoud y Mahmoud K. A. Khairat | Hibrido | P | – | logn (log(n/logn)) | – | – | – | |
2.002 | Spread | Steven J. Ross | Bucket – Merge – Radix | – | – | – | – | – | ||
2.003 | SheenkSort | Lei Yang, Hui Huang, Zheng Wan, y Tao Song | Bucket | P | – | – | – | – | – | |
2.003 | STXXL | Roman Dementiev y Peter Sanders | Merge – Radix | P | E | – | – | – | – | – |
2.004 | Library | Michael A. Bender, Martín Farach-Colton y Miguel Mosteiro | Inserción | I | (n) | (n²) | (n log n) | O(n) | Est | |
2.004 | Burst | Ranjan Sinha y Justin Zobel | Distribución – Bucket – Radix | – | O ( w × n ) | – | O ( w + n ) | – | ||
2.005 | GPUTeraSort | N. K. Govindaraju, J. Gray, R. Kumar y D. Manocha | Base de datos | P | E | – | – | – | – | – |
2.006 | 4FJ | M. Ayala-Rincόn, B.T. de Abreu, J. de Siqueira | Inserción – Fusión | I | – | – | – | – | – | |
2.006 | BSIS Pennysort | Xing Huang y BinHeng Song | Hibrido | (n) | – | – | – | – | ||
2.006 | GPU-Abisort | Alexander Greß y Gabriel Zachmann | Adaptative Bitonic | P | E | – | (n log n)/p | – | – | – |
2.006 | NeoSort | Chris Nyberg, Charles Koester ordinal Technology Corp. |
Hibrido | – | – | – | – | – | ||
2.006 | Pesort | Jing-Chao Chen | Samplesort – Quicksort | P | – | (n log² n) | (n log n) | – | – | |
2.006 | SS06 | K.K.Sudharajan y S.Chakraborty | Quicksort | I | (n²) | (n²) | (n log n) Aleatorio | – | – | |
2.007 | AA-(Aligned-Access) | Hiroshi Inoue, Takao Moriyama, Hideaki Komatsu y Toshio Nakatani | Comb – Merge | P | – | (n log n) | – | – | – | |
2.007 | Rank-Heapsort | Y. J. Wu y X.D. Wang | Heapsort | I | – | (n log n) − (0,788928n) | – | – | – | |
2.007 | LMM | Sanguthevar Rajasekaran | Bitonic – OEMS | P | E | – | – | – | – | – |
2.007 | Oz sort | Nikolas Askitis y Ranjan Sinha | Hibrido – Hash | I | – | – | – | – | – | |
2.007 | Quickparallel | Daniel Cederman y Philippas Tsigas | Quicksort | P | E | – | – | – | – | – |
2.007 | TokuSample Sort | Bradley C.Kuszmaul | División – Bucket | P | – | – | – | – | – | |
2.008 | Pancake | Hal Sudborough | Hibrido | – | (n) | (n) | O(log n) | No | ||
2.008 | GPUBucket | T. Rozen, K. Boryczko y W. Alda | Bucket | P | – | – | – | – | – | |
2.008 | GPUErikUlf | Erik Sintorn y Ulf Assarsson | Bucket – Quicksort + fusión | P | – | – | n log n | – | – | |
2.009 | IBR (Interval Based Rearrangement ) | Hagen Peters, Ole Schulz-Hildebrandt y Norbert Luttenberger | Adaptative Bitonic | P | E | – | – | – | – | – |
2.009 | Mapsort | Masato Edahiro | Mergesort – Quicksort | P | – | – | – | – | – | |
2.009 | DEMSort | Mirko Rahn, Peter Sanders, Johannes Singler y Tim Kieritz | Merge | P | – | – | – | – | – | |
2.009 | Dual Pivot | V. Yaroslavskiy | Quicksort | I | – | – | – | – | – | |
2.009 | GPUEOR | Bonan Huang, Jinlan Gao y Xiaoming Li | Radix | P | – | – | – | – | – | |
2.010 | DEMSort | Andreas Beckmann y Ulrich Meyer | Merge | P | – | – | – | – | – | |
2.010 | Flashsort | John D Davis y Suzanne Rivoire | Distribución | P | – | – | – | – | – | |
2.010 | GPUImplicit | Linh Ha, Jens Krüger y Cláudio T. Silva | Radix | P | – | – | – | – | – | |
2.011 | GPUMemSort | Yin Ye, Zhihui Du1, David A. Bader, Quan Yang y Weiwei Huo | División – Merge | P | – | – | – | – | – | |
2.011 | TritonSort | Alex Rasmussen, George Porter, Michael Conley, Radhika Niranjan Mysore, Amin Vahdat , Harsha V. Madhyastha y Alexander Pucher | División – Merge | P | E | – | – | – | – | – |
2.011 | Tritonsort | A. Rasmussen, G. Porter, M. Conley, H. V. Madhyastha, R. N. Mysore, A. Pucher y A. Vahdat. |
Hibrido | – | – | – | – | – | ||
2.011 | U | Upendra S. Aswal, Kamlesh C. Purohit y Sujata N. Thakur | Counting | I | (n) | (n²) | (n) | – | – | |
2.011 | pSort | Paolo Bertasi, Federica Bogo, Marco Bressan y Enoch Peserico | Merge | P | – | – | – | – | Est | |
2.012 | Counting Position | Nitin Arora, Banupriya S. Kumar y Vivek Kumar Tamta | Bucket | I | (n + r) | (n + r) | (n + r) | – | – | |
2.012 | Flat Datacenter Storage | Johnson Apacible, Rich Draves, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Ed Nightingale, Reuben Olinksy y Yutaka Suzue | Bucket | P | – | – | – | – | – | |
2.012 | GPUMerge | Davidson, Andrew, David Tarjan, Michael Garland, and John D. Owens, | Merge | P | – | – | – | – | – | |
2.012 | GPUMerge Path | Oded Green, Robert McColl y David A. Bader | Merge | P | – | – | – | – | – | |
2.012 | MPSM (B, D, P) | Martina-Cezara Albutiu, Alfons Kemper y Thomas Neumann | Radix – IntroSort – Quicksort | P | E | – | – | – | – | – |
2.012 | MQuickSort | A. L. Abu Dalhoum, T. Kobbay, A. Sleit, M. Alfonseca y A. Ortega | Quicksort | I | (n) | (n) | – | – | – | |
2.012 | IBR (Interval Based Rearrangement ) | Peters H, Schulz-Hildebrandt O, Luttenberger N | Adaptive Bitonic | P | – | – | – | – | – | |
2.012 | Radix | Zehra Yildz, Musa Aydin y Güray Yilmaz | Radix | P | E | – | – | – | – | – |
2.012 | Splay | Saikkonen y Soisalon-Soininen | Inserción – SplayTree | I | – | – | – | – | – | |
2.013 | Bitonic | Zehra Yildz, Musa Aydin y Güray Yilmaz | Bitonic | P | E | – | (logn)² | – | – | – |
2.013 | DeepSort | Zheng Li y Juan Lee Samsung | DeepSort | P | – | – | – | – | – | |
2.013 | Hyksort | H. Sundar, D. Malhotra y G. Biros | Hypercube Quicksort | P | – | – | – | – | – | |
2.013 | QuickXsort | Stefan Edelkamp y Armin Weiß | QuickHeapsort | I | ||||||
2.013 |
Adaptive Bitonic Sorting
|
Gabriel Zachmann | Bitonic | P |
(n log n)/p
|
– | – | (n log n) | – | |
2.013 | Novel | R. Shiriniwas y A. Raga Deepthi | Burbuja – Inserción | I | – | – | – | – | – | |
2.013 | Rotated-Library-sort | F. Lam y R.K. Wong | Inserción – Hibrido | I | – | – | – | – | – | |
2.013 | Teraflux-EU | Ivan Tanasic, Javier Cabezas, Isaac Gelado, Nacho Navarro y Wen-mei Hwu | Merge | P | – | – | – | – | – | |
2.014 | BaiduSort | Dasheng Jiang | Radix (LSD) – Quicksort – TritonSort | P | – | – | – | – | – | |
2.014 | GPUMatrix Sort | Mukul Panwar, Monu Kumar y Sanjay Bhargava | Merge | P | – | – | – | – | – | |
2.014 | NADSort | Qian Wang, Rong Gu, Yihua Huang, Reynold Xin, Wei Wu, Jun Song y Junluan Xia3 | División – Timsort – Merge | P | – | – | – | – | – | |
2.014 | Radix | Lukas Polok, Viorela Ila y Pavel Smrz | Radix | P | – | – | – | – | – | |
2.014 | TimSort | Reynold Xin, Parviz Deyhim, Xiangrui Meng, Ali Ghodsi y Matei Zaharia |
TimSort | P | – | – | – | – | – | |
2.014 | Zig-zag Sort | Michael T. Goodrich | Shellsort – AKS | (n log n) | – | – | – | – | ||
2.015 | AMS-sort | M. Axtmann, T. Bingmann, P. Sanders y C. Schulz | Samplesort | P | – | – | – | – | – | |
2.015 | Fuxi sort | Z. Zhang, C. Li, Y. Tao, R.Yang, H. Tang y J. Xu | Hibrido | P | – | – | – | – | – | |
2.015 | GPUkiliyu | Qi Mu, Liqing Cui y Yufei Song | Bitonic | P | – | – | – | – | – | |
2.015 | MP-sort | Y. Feng, M. Straka, T. di Matteo y R. Croft | Merge – Múltiple | P | – | – | – | – | – | |
2.015 | Tencent Sort | Jie Jiang, Lixiong Zheng, Junfeng Pu, Xiong Cheng, Chongqing Zhao, Mark R Nutter y Jeremy D Schaub | División – Merge | P | – | – | – | – | – | |
2.016 | Matrixsort | S. Kavitha, V. Vijay y A. B. Saketh | Hibrido | P | (n log√n) | (n²) | (n √n log√n) | – | – | |
2.016 | RAMS | Michael Axtmann y Peter Sanders | AMS-sort | P | – | – | – | – | – | |
2.016 | Sort Race | H. Zhang, B. Meng e Y. Liang | Quicksort – Fusión | I | – | – | – | – | – | |
2.018 | MQMS | Stefan Edelkamp y Armin Weiß | Quicksort – Mergesort | I | – | (n log n) | – | – | – | |
2.019 | NC-RealNumber | Yijie Han, Sneha Mishra y Md Usman Gani Syed | Hibrido | P | – | – | – | – | – | |
2.019 | HSS (Histogram sort with sampling) | Vipul Harsh, Laxmikant Kale y Edgar Solomonik | Sample sort – Histogram sort | P | – | – | – | – | – | |
– | Combinado (Cocktail – Burbuja bidireccional) | – | Intercambio – Burbuja | I | (n) | (n²) | (n²) | O(1) | Est | |
– | Bucket – Binsort (Cubeta) | – | Distribución – Pigeonhole (Casillero) | I | (n) | (n²) | (n+k) | O(n+k) | No |