El problema de miMerge.
El algoritmo (que de momento seguiré llamando miMerge, hasta que descubra si tiene otro nombre), tiene bastante en común con el Bitonic Mergesort, aunque este no ordena de forma tan “inteligente”. El Bitonic Mergesort, por otro lado tiene la ventaja de requerir un hardware más simple, y por lo tanto se usa para aprovechar su gran paralelización en GPU’s.
¿Y cual era el problema de miMerge? Al parecer efectivamente es asimptoticamente óptimo en el caso medio. También es optimo para vectores ya ordenados, pero heredá el gran fallo del merge sort original: utiliza o(n) memoría.
El bitonic mergesort sin embargo no tiene ese problema, pero a costa de pasar a un tiempo medio n log^2 n, que no es óptimo, y también será este su coste en el caso de vectores ordenados.
Así pues, parece que el gran problema de este algoritmo sigue estando en encontrar una función merge óptima, que sea in place. Puede que eso sea demasiado para mi… ya veremos.
April 30th, 2007 at 16:35
Hay mergesorts in-situ (es decir coste en espacio O(1)) pero no son fáciles…
S. Dvorák, B. Ďian: “Unstable linear time O(1) space merging”. The Computer Journal, vol.31, no.3, pp.279-282, 1988.
S. Dvorák, B. Ďian: “Stable linear time sublinear space merging”. The Computer Journal, vol.30, no.4, pp.372-375, 1987.
H. Mannila, E. Ukkonen: “A simple linear-time algorithm for in-situ merging”. Information Processing Letters, vol.18, no.4, pp.203-208, 1984.
A. Symvonis: “Optimal stable merging”. The Computer Journal, vol.38, no.8, pp.681-690, 1995 (al menos de éste se encuentra el pdf en google).
J. Ellis, M. Markov: “In situ, stable merging by way of the perfect shuffle”. The Computer Journal, vol.43, no.1 pp.40-53, 2000 (éste también se encuentra en google).
suerte
April 30th, 2007 at 16:40
ummmm quizás no… veo que los autores llaman “in-situ” a O(log^2 n)… bueno, ya tienes algo de lectura para empezar a mirar…
May 1st, 2007 at 18:32
Gracias por leer Javifields, parece que eres al único que le interesan un poco estos temas :P.
Lo que yo he leído de momento es que si que hay métodos “in-situ” del todo, pero que son tan complejos que aumentan la complejidad del algoritmo.
Por otro lado había pensado que al hacer merge tienes dos trozos de vector, a y b. Siguiendo con la filosofía del algoritmo general de “hacer lo mínimo posible” (es decir, ser vago y eficiente -¿Podría considerarse esto un esquema algoritmico?-), había pensado que lo que habría que hacer es coger el vector más pequeño, situar el máximo y el mínimo de ese vector comparándolos con los elementos del otro, y entonces ya tienes colocados todos los elementos que van hasta el mínimo y todos los que están a partir del máximo. Por lo tanto necesitas espacio auxiliar sólo para los elementos que te faltan por “colocar”.
En realidad todo esto lo haces con punteros, de modo que los datos que guardas, los guardas en el vector original, y con los que te falta comparar del vector “grande” los tienes en el vector original. Los único que necesitas conservar por separado son los del vector “pequeño”.
No sé si me explico, sino podría hacer otro dibujito con el paint :P.
De todas formas, creo que este método es el que usa el Timsort.
Estoy convencido de que es el método de ordenación óptimo para el 99% de los casos, así que voy a repasar el código esta tarde. Si tienes tiempo de echarle un ojo al algoritmo original dime que te parece.
Voy a echarles un ojo a los documentos.
May 1st, 2007 at 19:19
Puede parecer increíble, pero a los dos únicos que he conseguido acceder sin tener que “comprar” el artículo han sido:
J. Ellis, M. Markov: “In situ, stable merging by way of the perfect shuffle”. The Computer Journal, vol.43, no.1 pp.40-53, 2000
http://citeseer.ist.psu.edu/cache/papers/cs/7993/ftp:zSzzSzgodot.uvic.cazSzpubzSzPublicationszSzElliszSzmerge.pdf/ellis99insitu.pdf
y
A. Symvonis: “Optimal stable merging”. The Computer Journal, vol.38, no.8, pp.681-690, 1995
http://citeseer.ist.psu.edu/cache/papers/cs/3291/ftp:zSzzSzftp.cs.su.oz.auzSzpubzSztrzSzTR93_466.pdf/symvonis93optimal.pdf
Me parece una autentica VERGÜENZA que cualquier material de este tipo no sea de dominio público.
May 1st, 2007 at 19:57
En
A. Symvonis: “Optimal stable merging”. The Computer Journal, vol.38, no.8, pp.681-690, 1995
el algoritmo no sólo usa algo de espacio extra(O(log^2 n))
sino que además la complejidad del merge es n log n… lo que hace una complejidad para un mergesort que lo use n^2 log n, que claramente es mas lento que el caballo del malo.
en
J. Ellis, M. Markov: “In situ, stable merging by way of the perfect shuffle”. The Computer Journal, vol.43, no.1 pp.40-53, 2000
cada merge usa un buffer interno, aunque el método no lo entiendo.
February 5th, 2008 at 19:56
47a8b02983…
47a8b02983…