azrael

Lo que decía sobre la cota de los algoritmos de ordenación, explicado aquí con una bonita demostración.

Proof of the lower bound for the asymptotic running time of comparison sort algorithms

The worst case running time of any comparison sort algorithm is Ω(nlgn)

Let T be the decision tree for all possible comparisons between elements of a list . So T is complete and the label of each vertex v of the tree are of the form x_i:x_j and v is source of two edges labeled and < . The comparisons made by a sorting algorithm running over X corresponds to a path from the root of T to a leaf. One should note that for each possible permutation P of the elements in X there is such a path. So T has at least n! leaves. We know that T is a binary tree, so it has a maximum of 2^h leaves, where h is it’s height. We have and

.

Summarizing, h = Ω(nlgn)

Cada vez que pienso en ordenación y se me ocurre algo pienso que como lo hacía tan complicado, y que cómo lo complican tanto si es “tan fácil”.

Ordenar un vector de n elementos con k vectores ordenados en su interior, de forma óptima, viene a ser hallar en el mínimo tiempo posible la sorting network que caracteriza la ordenación de ese vector (por eso da igúal el tiempo de inserción suplementario a la búsqueda binaria, sólo ordenamos una vez que sabemos todas las relaciones entre elementos).

Ordenar un vector de n elementos con k vectores ordenados en su interior, el más largo de ellos de c elementos, es equivalente a ordenar los centros de de los k vectores (invocación recursiva al mismo algoritmo) y ordenar el elemento central a la izquierda del primer elemento ordenado con el central a la derecha del segundo ordenado etc… (búsqueda binaría de los centros de los k vectores en los demás de forma simultanea).

Mediante una búsqueda binaría simultanea masiva, de los elementos centrales de los k vectores, el coste sería:

ordenar(n)=(n-1)+ordenar(k)*log2(c)

En el peor caso (donde halla menos orden que aprovechar, vectores de 2 elementos)

ordenar(n)=(n-1)+ordenar( n/2)*log2(2)

P.D.: redondeando al entero superior log2(2)=1+1=2.