Referencia original para Huffman en forma de Merge Sort?

¿Cuál es la primera publicación del concepto de optimización de fusión ordenar por

1. identificar secuencias de posiciones consecutivas en órdenes crecientes (también conocidas como carreras) en tiempo lineal; entonces
2. fusionar repetidamente las dos secuencias más cortas y agregar el resultado de esta fusión a la lista de fragmentos ordenados.

En algunas de mis publicaciones (por ejemplo , http://barbay.cl/publications.html#STACS2009 , http://barbay.cl/publications.html#TCS2013 ) utilicé este truco para ordenar más rápido y generar una estructura de datos comprimida para permutación.

Parece que este truco se introdujo antes, solo en el contexto de una clasificación más rápida, pero ¿ni yo ni mi alumno hemos podido encontrar la referencia?

Encontré el resultado oculto en un oscuro informe técnico de 4p: comparto mis resultados aquí en caso de que otros estén interesados.

1. Knuth menciona carreras en su descripción del "tipo de fusión natural" (página 160 del tomo 3 de la 3ra edición), pero analiza su complejidad solo en promedio (lo que produce n / 2 carreras), no en función del número ρ de carreras
2. en 1985, Mannila demostró que Natural Mergesort toma tiempo dentro de O (n (1 + lg (r + 1))) para clasificar n elementos que forman r carreras.
3. en 1996, Tadao Takaoka ( http://dblp.uni-trier.de/pers/hd/t/Takaoka:Tadao ) introdujo la noción de la entropía de la distribución de los tamaños (n1, ..., nρ) de las corridas en un artículo técnico de 4 páginas titulado "Minimal MergeSort", y demostró una complejidad de comparaciones$n(1+2H(n1,…,nρ))$
4. en 2009, la técnica se presentó en el simposio Fundación matemática de ciencias de la computación (junto con los resultados en la clasificación, los caminos más cortos y los árboles de expansión mínima).
5. en 2010, se publicó en la revista Information Processing bajo el título "Entropía como complejidad computacional", con un coautor agregado, Yuji Nakagawa ( https://www.semanticscholar.org/author/Yuji-Nakagawa/2219943 ) .

Me uno a las referencias bibtex a continuación.

@TechReport {1997-TR-MinimalMergesort-Takaoka, autor = {Tadao Takaoka}, título = {Minimal Mergesort}, institución = {Universidad de Canterbury}, año = 1997, nota = { http://ir.canterbury.ac. nz / handle / 10092/9676 , último acceso [23/08/2016 Tue]}, abstract = {Presentamos un nuevo algoritmo de ordenamiento adaptativo, denominado ordenamiento de fusión mínima, que combina las ejecuciones ascendentes en la lista de entrada de menor a mayor, es decir, fusionando las dos listas más cortas cada vez. Mostramos que este algoritmo es óptimo con respecto a la nueva medida de preselección, llamada entropía.}}

En este artículo presentamos la medida de entropía H (S) para la incertidumbre en datos de entrada parcialmente resueltos S (X) = (X 1, ..., X k), donde X es el conjunto de datos completo, y cada X i es Ya resuelto. Utilizamos la medida de entropía para analizar tres problemas de ejemplo, clasificación, caminos más cortos y árboles de expansión mínima. Para ordenar X i es una carrera ascendente, y para caminos más cortos, X i es una parte acíclica en el gráfico dado. Para árboles de expansión mínima, X i se interpreta como un árbol de expansión mínima parcialmente obtenido para un subgrafo. La medida de entropía, H (S), se define con respecto a pi = | X i | / | X | como medida de probabilidad, es decir, H (S) = - nΣki = 1pilogpi, donde n = Σki = 1 | Xi |. Luego mostramos que podemos ordenar los datos de entrada S (X) en el tiempo O (H (S)), y resolver el problema de la ruta más corta en el tiempo O (m + H (S)) donde m es el número de bordes de la grafico.

@article {2010-JIP-EntropyAsComputationalComplexity-TakaokaNakagawa, author = {Tadao Takaoka and Yuji Nakagawa}, title = {Entropy as Computational Complexity}, journal = jip, volume = {18}, pages = {227--241}, year = {2010}, url = { http://dx.doi.org/10.2197/ipsjjip.18.227 }, doi = {10.2197 / ipsjjip.18.227}, marca de tiempo = {mié, 14 de septiembre de 2011 13:30:52 +0200 }, biburl = { http://dblp.uni-trier.de/rec/bib/journals/jip/TakaokaN10 }, bibsource = {dblp bibliografía informática, http://dblp.org}, abstract = {Si la instancia del problema dada se resuelve parcialmente, queremos minimizar nuestro esfuerzo para resolver el problema utilizando esa información. En este artículo presentamos la medida de entropía, H (S), para la incertidumbre en los datos de entrada parcialmente resueltos S (X) = (X1,..., Xk), donde X es el conjunto de datos completo, y cada Xi ya está resuelto Proponemos un algoritmo genérico que combina Xi repetidamente y termina cuando k se convierte en 1. Usamos la medida de entropía para analizar tres problemas de ejemplo, clasificación, caminos más cortos y árboles de expansión mínima. Para clasificar Xi es una carrera ascendente, y para árboles de expansión mínima, Xi se interpreta como un árbol de expansión mínima parcialmente obtenido para un subgrafo. Para los caminos más cortos, Xi es una parte acíclica en el gráfico dado. Cuando k es pequeño, el gráfico puede considerarse casi acíclico. La medida de entropía, H (S), se define con respecto a pi = ¦Xi¦ / ¦X¦ como una medida de probabilidad, es decir, H (S) = -n (p1 log p1 +... + pk log pk), donde n = ¦X1¦ +. . . + ¦Xk¦. Mostramos que podemos ordenar los datos de entrada S (X) en el tiempo O (H (S)), y que podemos completar el árbol de expansión de costo mínimo en el tiempo O (m + H (S)), donde m en el número de bordes Luego resolvemos el problema del camino más corto en el tiempo O (m + H (S)). Finalmente, definimos la entropía dual en el proceso de partición, mediante el cual damos los límites de tiempo en una clasificación rápida genérica y el problema de la ruta más corta para otro tipo de gráficos casi acíclicos.} donde m en el número de aristas. Luego resolvemos el problema del camino más corto en el tiempo O (m + H (S)). Finalmente, definimos la entropía dual en el proceso de partición, mediante el cual damos los límites de tiempo en una clasificación rápida genérica y el problema de la ruta más corta para otro tipo de gráficos casi acíclicos.} donde m en el número de aristas. Luego resolvemos el problema del camino más corto en el tiempo O (m + H (S)). Finalmente, definimos la entropía dual en el proceso de partición, mediante el cual damos los límites de tiempo en una clasificación rápida genérica y el problema de la ruta más corta para otro tipo de gráficos casi acíclicos.}
}