Ordenación de Vectores II

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